Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Юджин Лейтон (Джин) Лоулер
Родившийся1933 г. ( 1933 )
Умер2 сентября 1994 г.
НациональностьАмериканец
Научная карьера
Поляинформатика , биология
Известные студентыДэвид Шмойс , Тэнди Варнов

Юджин Лейтон (Джин) Лоулер (1933 - 2 сентября 1994) был американским ученым-компьютерщиком , профессором информатики в Калифорнийском университете в Беркли . [1] [2]

Академическая жизнь [ править ]

Лоулер приехал в Гарвард как аспирант в 1954 году после трехлетнего обучения по программе бакалавриата по математике в Университете штата Флорида . Он получил степень магистра в 1957 г. [2] и взял перерыв в учебе, во время которого он ненадолго поступил на юридический факультет и работал в армии США, в компании по производству шлифовальных кругов [3] и инженером-электриком в Сильвании. с 1959 по 1961 год. [2] [4] Он вернулся в Гарвард в 1958 году и защитил докторскую диссертацию. в 1962 г. под руководством Энтони Г. Эттингера с диссертацией « Некоторые аспекты дискретного математического программирования» . [2] [5]Затем он стал преподавателем в Мичиганском университете до 1971 года, когда переехал в Беркли. [2] Он вышел на пенсию в 1994 году, незадолго до своей смерти. [6]

В Беркли среди докторантов Лоулера были Маршал Берн, Чип Мартел , Арвинд Рагхунатан, Арни Розенталь, Хузур Саран, Дэвид Шмойс и Тэнди Варнов . [5] [7]

Исследование [ править ]

Лоулер был экспертом по комбинаторной оптимизации и основателем этой области [8], автором широко используемого учебника « Комбинаторная оптимизация: сети и матроиды» и соавтором книги «Задача коммивояжера: экскурсия по комбинаторной оптимизации» . Он сыграл центральную роль в спасении метода эллипсоидов для линейного программирования от безвестности на Западе. [1] [9] Он также написал (вместе с Д. Е. Вудом) широко цитируемый обзор алгоритмов ветвлений и границ в 1966 г. [10], выбранный в качестве классического цитирования в 1987 г. [2], и еще одну важную раннюю статью по динамическому программированиюс Дж. М. Муром. [2] [11] Лоулер также первым заметил, что пересечение матроидов может быть решено за полиномиальное время . [1] [12]

В NP-полноте доказательство для двух из 21 NP-полных задач Карпа , направлены гамильтон цикл и 3-мерное соответствие , было кредитуется Karp к Лоулеру. [1] NP-полнота трехмерного сопоставления является примером одного из любимых наблюдений Лоулера, «мистической силы двойственности»: [1] для многих задач комбинаторной оптимизации, которые могут быть параметризованы целым числом, проблема может быть решается за полиномиальное время, когда параметр равен двум, но становится NP-полным, когда параметр равен трем. Для 3-мерного сопоставления решаемой версией задачи с параметром 2 является сопоставление графов.; то же явление возникает при сложностях 2-раскраски и 3-раскраски для графов, в проблеме пересечения матроидов для пересечений двух или трех матроидов и в 2-SAT и 3-SAT для задач выполнимости . Ленстра [1] пишет, что «Джин неизменно комментировал бы, что именно поэтому был разработан мир с двумя полами».

В 1970-е годы Лоулер добился больших успехов в систематизации алгоритмов планирования работы цехов . [1] Его обзор 1979 года по этому вопросу ввел трехполевую нотацию для теоретических задач планирования , которая (несмотря на существование более ранних обозначений) стала стандартом при изучении алгоритмов планирования. [13] [14] Другой более поздний обзор также получил высокую оценку (более 1000 цитирований в Google Scholar). [15]

В конце 1980-х Лоулер переключил свои исследования на проблемы вычислительной биологии , включая реконструкцию эволюционных деревьев и несколько работ по выравниванию последовательностей . [2]

Социальная активность [ править ]

Весной 1969 года, находясь в творческом отпуске в Беркли, Лоулер принял участие в акции протеста против войны во Вьетнаме, которая привела к аресту 483 протестующих, включая Лоулера; [3] Ричард Карп выручил его. [6] Карп вспоминает Лоулера как «общественное сознание отдела CS, всегда заботящееся о благополучии студентов и особенно заботящееся о женщинах, меньшинствах и студентах-инвалидах». [6]

Награды и награды [ править ]

В 1998 году чести Лоулера был посвящен специальный выпуск журнала Mathematical Programming (том 82, выпуски 1-2) [8].

Премия ACM Eugene L. Lawler вручается Ассоциацией вычислительной техники каждые два года за «гуманитарный вклад в области информатики и информатики». [16]

Книги [ править ]

  • Комбинаторная оптимизация: сети и матроиды (Холт, Райнхарт и Уинстон, 1976, [17] ISBN  978-0-03-084866-7 , переиздано Dover Books в 2001 году, ISBN 978-0-486-41453-9 ). Ленстра и Шмойс пишут, что эта книга является классической и «она помогла сформировать развивающуюся область исследований». [8] 
  • Задача коммивояжера: экскурсия по комбинаторной оптимизации (совместно с JK Lenstra , AHG Rinnooy Kan и D. Shmoys, Wiley, 1985, ISBN 978-0-471-90413-7 ). 
  • Избранные публикации Юджина Л. Лоулера ( К. Аардал , Дж. К. Ленстра, Ф. Маффиоли и Д. Шмойс , ред., CWI Tracts 126, Centrum Wiskunde & Informatica , 1999, ISBN 978-90-6196-484-1 ). Отпечатки 26 научных работ Лоулера. 

Ссылки [ править ]

  1. ^ a b c d e f g Ленстра, Ян Карел (1998), «Мистическая сила двойственности: память Юджина Л. Лоулера» , Journal of Scheduling , 1 (1): 3–14, doi : 10.1002 / (SICI ) 1099-1425 (199806) 1: 1 <3 :: AID-JOS1> 3.0.CO; 2-B.
  2. ^ a b c d e f g h Гасфилд, Дэн; Шмойс, Давид ; Ленстра, Ян Карел ; Варнов, Тэнди (1994), "Память Евгений Л. Лолер", Журнал вычислительной биологии , 1 (4): 255-256, DOI : 10,1089 / cmb.1994.1.255. Печатается в Райс Univ, корпоративный (1994), "Памяти Евгения Л. Лоулера", SIGACT News , 25 (4): 108-109, DOI : 10,1145 / 190616,190626 , S2CID 5267081 .
  3. ^ a b Лоулер, EL (1991), «Старые рассказы», ​​в Ленстре, JK ; Ринну Кан, AHG ; Schrijver, A. (eds.), History of Mathematical Programming: A Collection of Personal Reminiscences , North-Holland, pp. 97–106..
  4. ^ Редакция (1995) In Memoriam: Юджин Л. Лоулер , SIAM Journal on Computing 24 (1), 1-2.
  5. ^ a b Юджин Лейтон Лоулер в проекте « Математическая генеалогия» .
  6. ^ a b c Карп, Ричард (2003), Личный взгляд на компьютерные науки в Беркли , Департамент EECS, Калифорнийский университет, Беркли.
  7. ^ Теоретическая информатика академическая генеалогия , Ян Парберри, 1996, извлечено 2010-09-17.
  8. ^ a b c Ленстра, Ян Карел ; Schmoys, Дэвид (1998), "Предисловие", Математическое программирование , 82 (1-2): 1, DOI : 10.1007 / BF01585862.
  9. ↑ Браун, Малкольм В. (7 ноября 1979 г.), «Советское открытие потрясает мир математики: сообщается о неожиданном открытии, которое помогло решить русские задачи», New York Times.
  10. ^ Лоулер, EL; Вуд, DE (1966), "ветвей и оценка методов: обследование", исследование операций , 14 (4): 699-719, DOI : 10,1287 / opre.14.4.699 , JSTOR 168733 .
  11. ^ Лоулер, EL; Мур, JM (1969), "Функциональное уравнение и его применение к задачам распределения ресурсов и упорядочивания", Управление науки , 16 (1): 77-84, DOI : 10,1287 / mnsc.16.1.77 , JSTOR 2628367 .
  12. ^ Лоулер, Л. (1975), "алгоритмы пересечения матроиды", Математическое программирование , 9 (1): 31-56, DOI : 10.1007 / BF01681329 , S2CID 206801650 .
  13. ^ Грэм, Рональд Л .; Лоулер, Юджин Л .; Ленстра, Ян К .; Ринну Кан, AHG (1979), «Оптимизация и аппроксимация в детерминированной последовательности и планировании: обзор», Дискретная оптимизация I: труды Института перспективных исследований по дискретной оптимизации и системным приложениям , Анналы дискретной математики, 4 , Северная Голландия, п. 287.
  14. ^ Т'киндт, Винсент; Билло, Жан-Шарль (2002), Многокритериальное планирование: теория, модели и алгоритмы , Springer-Verlag, стр. 16, ISBN 978-3-540-43617-1.
  15. ^ Лоулер, Юджин Л .; Ленстра, Ян К .; Ринну Кан, AHG ; Шмойс, Дэвид Б. (1993), «Последовательность и планирование: алгоритмы и сложность», в Graves, SC; Ринну Кан, AHG ; Зипкин, Пол Герберт (ред.), Логистика производства и инвентаризация , Справочники по исследованию операций и науке об управлении, 4 , Северная Голландия, стр. 445–522..
  16. ^ Евгений Л. Лоулер премия , ACM, извлекается 2010-09-14.
  17. ^ Беллман, RE (1978). "Обзор: Комбинированная оптимизация: сети и матроиды , Юджин Л. Лоулер" . Бык. Амер. Математика. Soc . 84 (3): 461–463. DOI : 10,1090 / s0002-9904-1978-14493-0 .

Внешние ссылки [ править ]

  • Лоулер в 1977 году , из коллекции фотографий Обервольфаха.