Юджин Лоулер
Юджин Лейтон (Джин) Лоулер | |
|---|---|
| Рожденный | 1933 |
| Умер | 2 сентября 1994 г. |
| Национальность | Американский |
| Научная карьера | |
| Поля | информатика , биология |
| Известные студенты | Дэвид Шмойс , Тэнди Уорноу |
Юджин Лейтон (Джин) Лоулер (1933 — 2 сентября 1994) — американский учёный-компьютерщик и профессор информатики в Калифорнийском университете в Беркли . [1] [2]
Академическая жизнь [ править ]
Лоулер приехал в Гарвард в качестве аспиранта в 1954 году, после трехлетней программы бакалавриата по математике в Университете штата Флорида . В 1957 году получил степень магистра. [2] и взял перерыв в учебе, во время которого он ненадолго поступил на юридический факультет и работал в армии США, в компании по производству шлифовальных кругов, [3] и инженером-электриком в Сильвании с 1959 по 1961 год. [2] [4] Он вернулся в Гарвард в 1958 году и защитил докторскую диссертацию. по прикладной математике в 1962 году под руководством Энтони Г. Эттингера, защитив диссертацию на тему «Некоторые аспекты дискретного математического программирования» . [1] [2] [5] Затем он стал преподавателем Мичиганского университета до 1971 года, когда переехал в Беркли. [2] Он вышел на пенсию в 1994 году, незадолго до своей смерти. [6]
В Беркли среди докторантов Лоулера были Маршалл Берн, Чип Мартел , Арвинд Рагунатан, Арни Розенталь, Хузур Саран, Дэвид Шмойс и Тэнди Уорноу . [5] [7]
Исследования [ править ]
Лоулер был экспертом по комбинаторной оптимизации и основателем этой области. [8] автор широко используемого учебника « Комбинаторная оптимизация: сети и матроиды» и соавтор книги «Задача коммивояжера: экскурсия по комбинаторной оптимизации» . Он сыграл центральную роль в спасении эллипсоидного метода линейного программирования от безвестности на Западе. [1] [9] Он также написал (совместно с Д.Э. Вудом) широко цитируемый обзор 1966 года по алгоритмам ветвей и границ : [10] выбран в качестве классического цитирования в 1987 году, [2] и еще одна влиятельная ранняя статья по динамическому программированию с Дж. М. Муром. [2] [11] Лоулер был также первым, кто заметил, что пересечение матроидов может быть решено за полиномиальное время . [1] [12]
Доказательства NP -полноты для двух из 21 NP-полной задачи Карпа , направленного гамильтонова цикла и трехмерного паросочетания , были приписаны Карпом Лоулеру. [1] NP-полнота трехмерного сопоставления — пример одного из любимых наблюдений Лоулера — «мистической силы двойственности»: [1] для многих задач комбинаторной оптимизации, которые могут быть параметризованы целым числом, проблема может быть решена за полиномиальное время , когда параметр равен двум, но становится NP-полной, когда параметр равен трем. Для трехмерного сопоставления решаемой версией проблемы с параметром 2 является сопоставление по графу ; то же явление возникает в сложностях 2-раскраски и 3-раскраски графов, в задаче пересечения матроидов для пересечений двух или трех матроидов, а также в 2-SAT и 3-SAT для задач выполнимости . Ленстра [1] пишет, что «Джин неизменно комментировал, что именно поэтому был создан мир с двумя полами».
В 1970-е годы Лоулер добился больших успехов в систематизации алгоритмов планирования работы цехов . [1] В его обзоре 1979 года на эту тему была введена трехполевая нотация для теоретических задач планирования , которая (несмотря на существование более ранних обозначений) стала стандартной при изучении алгоритмов планирования. [13] [14] Еще один более поздний опрос также широко цитируется (более 1000 цитирований каждый в Google Scientific). [15]
В конце 1980-х годов Лоулер переключил фокус своих исследований на проблемы вычислительной биологии , включая реконструкцию эволюционных деревьев и несколько работ по выравниванию последовательностей . [2]
активизм Социальный
Весной 1969 года, находясь в творческом отпуске в Беркли, Лоулер принял участие в акции протеста против войны во Вьетнаме , которая привела к арестам 483 протестующих, включая Лоулера; [3] Ричард Карп выручил его. [6] Карп вспоминает Лоулера как «общественного сознания Отделения CS, всегда заботящегося о благополучии студентов и особенно заботящегося о женщинах, меньшинствах и студентах с ограниченными возможностями». [6]
Награды и почести [ править ]
В 1998 году в честь Лоулера был посвящен специальный выпуск журнала Mathematical Programming (том 82, выпуски 1–2). [8]
Премия ACM Юджина Л. Лоулера вручается Ассоциацией вычислительной техники каждые два года за «гуманитарный вклад в области информатики и информатики». [16]
Книги [ править ]
- Комбинаторная оптимизация: сети и матроиды (Холт, Райнхарт и Уинстон, 1976, [17] ISBN 978-0-03-084866-7 , переизданный Dover Books в 2001 г., ISBN 978-0-486-41453-9 ). Ленстра и Шмойс пишут, что эта книга является классической и что «она помогла сформировать новую область исследований». [8]
- Задача коммивояжера: экскурсия по комбинаторной оптимизации (совместно с Дж. К. Ленстрой , АХГ Риннуем Каном и Д. Шмойсом, Wiley, 1985, ISBN 978-0-471-90413-7 ).
- Избранные публикации Юджина Л. Лоулера ( К. Аардал , Дж. К. Ленстра, Ф. Маффиоли и Д. Шмойс , ред., CWI Tracts 126, Centrum Wiskunde & Informatica , 1999, ISBN 978-90-6196-484-1 ). Перепечатки 26 исследовательских работ Лоулера.
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и ж г час Ленстра, Ян Карел (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 , S2CID 62210683 .
- ^ Jump up to: Перейти обратно: а б с д и ж г час Гасфилд, Дэн; Шмойс, Дэвид ; Ленстра, Ян Карел ; Варноу, Тэнди (1994), «Памяти Юджина Л. Лоулера», Журнал вычислительной биологии , 1 (4): 255–256, doi : 10.1089/cmb.1994.1.255 . Перепечатано в Rice Univ, Corporate (1994), «Памяти Юджина Л. Лоулера», SIGACT News , 25 (4): 108–109, doi : 10.1145/190616.190626 , S2CID 5267081 .
- ^ Jump up to: Перейти обратно: а б Лоулер, Э.Л. (1991), «Старые истории», в Ленстре, Дж. К .; Риннуй Кан, AHG ; Шрийвер А. (ред.), История математического программирования: сборник личных воспоминаний , Северная Голландия, стр. 97–106 .
- ^ Редакция (1995) В память: Юджин Л. Лоулер , SIAM Journal on Computing 24 (1), 1-2.
- ^ Jump up to: Перейти обратно: а б Юджин Лейтон Лоулер в проекте «Математическая генеалогия» .
- ^ Jump up to: Перейти обратно: а б с Карп, Ричард (2003), Личный взгляд на информатику в Беркли , факультет EECS, Калифорнийский университет, Беркли .
- ^ Академическая генеалогия теоретической информатики , Ян Парберри, 1996, получено 17 сентября 2010 г.
- ^ Jump up to: Перейти обратно: а б с Ленстра, Ян Карел ; Шмойс, Дэвид (1998), «Предисловие», Mathematical Programming , 82 (1–2): 1, doi : 10.1007/BF01585862 .
- ^ Браун, Малкольм В. (7 ноября 1979 г.), «Советское открытие потрясло мир математики: сообщалось о неожиданном открытии русских в области решения задач», The New York Times .
- ^ Лоулер, Эл.; Вуд, DE (1966), «Методы ветвей и границ: исследование», Operations Research , 14 (4): 699–719, doi : 10.1287/opre.14.4.699 , JSTOR 168733 .
- ^ Лоулер, Эл.; Мур, Дж. М. (1969), «Функциональное уравнение и его применение к задачам распределения ресурсов и последовательности», Management Science , 16 (1): 77–84, doi : 10.1287/mnsc.16.1.77 , JSTOR 2628367 .
- ^ Лоулер, Э.Л. (1975), «Алгоритмы пересечения матроидов», Mathematical Programming , 9 (1): 31–56, doi : 10.1007/BF01681329 , S2CID 206801650 .
- ^ Грэм, Рональд Л .; Лоулер, Юджин Л.; Ленстра, Ян К .; Риннуй Кан, AHG (1979), «Оптимизация и аппроксимация в детерминированном последовательном построении и планировании: обзор», Дискретная оптимизация I: труды Института перспективных исследований по дискретной оптимизации и системным приложениям , Анналы дискретной математики, том. 4, Северная Голландия, с. 287 .
- ^ Т'киндт, Винсент; Бийо, Жан-Шарль (2002), Многокритериальное планирование: теория, модели и алгоритмы , Springer-Verlag, с. 16, ISBN 978-3-540-43617-1 .
- ^ Лоулер, Юджин Л.; Ленстра, Ян К .; Риннуй Кан, AHG ; Шмойс, Дэвид Б. (1993), «Последовательность и планирование: алгоритмы и сложность», в Грейвсе, Южная Каролина; Риннуй Кан, AHG ; Зипкин, Пол Герберт (ред.), Логистика производства и запасов , Справочники по исследованию операций и науке управления, том. 4, Северная Голландия, стр. 445–522 .
- ^ Премия Юджина Л. Лоулера , ACM, получено 14 сентября 2010 г.
- ^ Беллман, Р.Э. (1978). «Обзор: Комбинационная оптимизация: сети и матроиды , Юджин Л. Лоулер» . Бык. амер. Математика. Соц . 84 (3): 461–463. дои : 10.1090/s0002-9904-1978-14493-0 .
Внешние ссылки [ править ]
- Лоулер в 1977 году , из коллекции фотографий Обервольфаха.
| Международный | |
|---|---|
| Национальный | |
| академики | |
| Другой | |
