Юджин Лоулер - Eugene Lawler

Юджин Лейтон (Джин) Лоулер
Родившийся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-мерное соответствие, были приписаны Карпом Лоулеру.[1] NP-полнота 3-мерного сопоставления является примером одного из любимых наблюдений Лоулера, «мистической силы двойственности»:[1] для многих задач комбинаторной оптимизации, которые могут быть параметризованы целым числом, проблема может быть решена в полиномиальное время когда параметр равен двум, но становится NP-полным, когда параметр равен трем. Для 3-мерного сопоставления вариант задачи с разрешимым параметром 2 имеет вид сопоставление графиков; то же явление возникает в сложностях 2-раскраска и 3-раскраска для графов, в задаче о пересечении матроидов для пересечений двух или трех матроидов, и в 2-СБ и 3-СБ за проблемы выполнимости. Ленстра[1] пишет, что «Джин неизменно комментировал бы, что именно поэтому был разработан мир с двумя полами».

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

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

Социальная активность

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

Награды и отличия

Спецвыпуск журнала Математическое программирование (том 82, выпуски 1-2) был посвящен в честь Лоулера в 1998 году.[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 научных работ Лоулера.

Рекомендации

  1. ^ а б c d е ж грамм Ленстра, Ян Карел (1998), «Мистическая сила двойственности: память Юджина Л. Лоулера», Журнал планирования, 1 (1): 3–14, Дои:10.1002 / (SICI) 1099-1425 (199806) 1: 1 <3 :: AID-JOS1> 3.0.CO; 2-B.
  2. ^ а б c d е ж грамм час Гасфилд, Дэн; Шмойс Давид; Ленстра, Ян Карел; Варнов, Тэнди (1994), «Памяти Юджина Л. Лоулера», Журнал вычислительной биологии, 1 (4): 255–256, Дои:10.1089 / cmb.1994.1.255. Перепечатано в Rice Univ, Corporate (1994), "Памяти Юджина Л. Лоулера", Новости SIGACT, 25 (4): 108–109, Дои:10.1145/190616.190626, S2CID  5267081.
  3. ^ а б Лоулер, Э. Л. (1991), «Старые рассказы», ​​в Ленстра, Дж. К.; Риннуй Кан, А. Х. Г.; Шрайвер, А. (ред.), История математического программирования: сборник личных воспоминаний, Северная Голландия, стр. 97–106..
  4. ^ Редакция (1995 г.) Памяти: Юджина Л. Лоулера, SIAM Журнал по вычислениям 24(1), 1-2.
  5. ^ а б Юджин Лейтон Лоулер на Проект "Математическая генеалогия".
  6. ^ а б c Карп, Ричард (2003), Личный взгляд на компьютерные науки в Беркли, Департамент EECS, Калифорнийский университет, Беркли.
  7. ^ Теоретическая информатика академическая генеалогия, Ян Парберри, 1996 г., получено 17 сентября 2010 г.
  8. ^ а б c Ленстра, Ян Карел; Шмойс, Дэвид (1998), «Предисловие», Математическое программирование, 82 (1–2): 1, Дои:10.1007 / BF01585862.
  9. ^ Браун, Малкольм У. (7 ноября 1979 г.), «Советское открытие потрясло мир математики: сообщается об открытии, которое неожиданно для себя решает Россия», Нью-Йорк Таймс.
  10. ^ Lawler, E. L .; Вуд, Д. Э. (1966), "Методы ветвей и границ: обзор", Исследование операций, 14 (4): 699–719, Дои:10.1287 / opre.14.4.699, JSTOR  168733.
  11. ^ Lawler, E. L .; Мур, Дж. М. (1969), "Функциональное уравнение и его применение к задачам распределения ресурсов и последовательности", Наука управления, 16 (1): 77–84, Дои:10.1287 / mnsc.16.1.77, JSTOR  2628367.
  12. ^ Лоулер, Э. Л. (1975), "Алгоритмы пересечения матроидов", Математическое программирование, 9 (1): 31–56, Дои:10.1007 / BF01681329, S2CID  206801650.
  13. ^ Грэм, Рональд Л.; Лоулер, Юджин Л .; Ленстра, Ян К.; Риннуй Кан, А. Х. Г. (1979), "Оптимизация и приближение в детерминированном упорядочивании и планировании: обзор", Дискретная оптимизация I: труды Института перспективных исследований по дискретной оптимизации и системным приложениям, Анналы дискретной математики, 4, Северная Голландия, стр. 287.
  14. ^ Т'киндт, Винсент; Билло, Жан-Шарль (2002), Многокритериальное планирование: теория, модели и алгоритмы, Springer-Verlag, стр. 16, ISBN  978-3-540-43617-1.
  15. ^ Лоулер, Юджин Л .; Ленстра, Ян К.; Риннуй Кан, А. Х. Г.; Шмойс, Дэвид Б. (1993), «Последовательность и планирование: алгоритмы и сложность», в Graves, S.C .; Риннуй Кан, А. Х. Г.; Зипкин, Пол Герберт (ред.), Логистика производства и инвентаризация, Справочники по исследованию операций и науке управления, 4, Северная Голландия, стр. 445–522..
  16. ^ Премия Юджина Л. Лоулера, ACM, получено 14 сентября 2010 г.
  17. ^ Беллман, Р.Э. (1978). "Рассмотрение: Комбинированная оптимизация: сети и матроидыЮджина Л. Лоулера ". Бык. Амер. Математика. Soc. 84 (3): 461–463. Дои:10.1090 / s0002-9904-1978-14493-0.

внешняя ссылка