Войти
| Юджин Лейтон (Джин) Лоулер | |
|---|---|
| Родился | 1933 (1933) |
| Умер | 2 сентября 1994 г. |
| Национальность | Американец |
| Научная карьера | |
| Филдс | информатика, биология |
| Известные студенты | Дэвид Шмойс, Тэнди Уорноу |
Юджин Лейтон (Джин) Лоулер (1933 - 2 сентября 1994), американский ученый-компьютерщик, профессор информатики в Калифорнийском университете в Беркли.
Лоулер пришел в Гарвард в качестве аспиранта в 1954 году после трехлетнего бакалавриата. программа по математике в Государственном университете Флориды. Он получил степень магистра в 1957 году и взял перерыв в учебе, во время которого он ненадолго поступил на юридический факультет и работал в армии США, в компании по производству шлифовальных кругов и инженером-электриком в Sylvania с 1959 по 1961 год. Он вернулся в Гарвард в 1958 году и защитил докторскую диссертацию. в 1962 году под руководством Энтони Г. Эттингера защитил диссертацию на тему «Некоторые аспекты дискретного математического программирования». Затем он стал преподавателем в Мичиганском университете до 1971 года, когда он переехал в Беркли. Он вышел на пенсию в 1994 году, незадолго до своей смерти.
В Беркли среди докторантов Лоулера были Маршал Берн, Чип Мартел, Арвинд Рагхунатан, Арни Розенталь, Хузур Саран, Дэвид Шмойс и Тэнди Уорноу.
Лоулер был экспертом по комбинаторной оптимизации и основателем этой области, автором широко используемого учебника «Комбинаторная оптимизация: сети». и Matroids и соавтор проблемы коммивояжера: экскурсия по комбинаторной оптимизации. Он сыграл центральную роль в спасении метода эллипсоидов для линейного программирования от безвестности на Западе. Он также написал (вместе с Д. Е. Вудом) широко цитируемый обзор алгоритмов ветвей и границ 1966 года, выбранный в качестве классического цитирования в 1987 году, и еще одну влиятельную раннюю статью по динамическому программированию с Дж.. Лоулер также был первым, кто заметил, что пересечение матроидов может быть решено за полиномиальное время.
Доказательства NP-полноты для двух из 21 NP-полных Карпа. задачи, направленный гамильтонов цикл и трехмерное сопоставление были приписаны Карпом Лоулеру. NP-полнота трехмерного сопоставления - это пример одного из любимых наблюдений Лоулера, «мистической силы двойственности»: для многих задач комбинаторной оптимизации, которые можно параметризовать целым числом, проблема может быть решена в полиноме time, когда параметр равен двум, но становится NP-полным, когда параметр равен трем. Для 3-мерного сопоставления разрешимая версия проблемы с параметром 2 - это сопоставление графов ; то же самое явление возникает в сложностях 2-раскраски и 3-раскраски для графов, в задаче пересечения матроидов для пересечений двух или трех матроидов и в 2- SAT и 3-SAT для проблем выполнимости. Ленстра пишет, что «Джин неизменно комментировал бы, что именно поэтому был разработан мир с двумя полами».
В 1970-е годы Лоулер добился больших успехов в систематизации алгоритмов планирования работы цехов. В его обзоре 1979 г. на эту тему была введена трехполевая нотация для теоретических задач планирования, которая (несмотря на существование более ранних обозначений) стала стандартной при изучении алгоритмов планирования. Еще один более поздний обзор также широко цитируется (более 1000 цитирований в каждом ученом Google).
В конце 1980-х Лоулер переключил свое внимание на проблемы вычислительной биологии, включая реконструкцию эволюционных деревьев и несколько работ по выравниванию последовательностей.
Весной 1969 года, находясь в творческом отпуске в Беркли, Лоулер принял участие в протесте против войны во Вьетнаме. это привело к аресту 483 протестующих, в том числе Лоулера; Ричард Карп спас его. Карп вспоминает Лоулера как «общественное сознание подразделения CS, всегда заботящееся о благополучии студентов и особенно заботящееся о женщинах, меньшинствах и студентах-инвалидах».
Особый выпуск журнала Mathematical Programming (том 82, выпуски 1-2) был посвящен в честь Лоулера в 1998 году.
Премия ACM Eugene L. Lawler Award является выдается Ассоциацией вычислительной техники каждые два года за «гуманитарный вклад в информатику и информатику».
