Юджин Лейтон (Джин) Лоулер (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]