Юджин Лейтон (Джин) Лоулер (1933 – 2 сентября 1994) был американским учёным-компьютерщиком и профессором компьютерных наук в Калифорнийском университете в Беркли . [1] [2]
Лоулер приехал в Гарвард в качестве аспиранта в 1954 году после трехлетней программы бакалавриата по математике в Университете штата Флорида . Он получил степень магистра в 1957 году, [2] и сделал перерыв в учебе, во время которого он ненадолго поступил в юридическую школу и работал в армии США, в компании по производству шлифовальных кругов, [3] и инженером-электриком в Sylvania с 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-полных задач Карпа , направленного гамильтонова цикла и 3-мерного сопоставления , были приписаны Карпом Лоулеру. [1] NP-полнота 3-мерного сопоставления является примером одного из любимых наблюдений Лоулера, «мистической силы двойственности»: [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 Division, всегда заботящуюся о благополучии студентов и особенно обеспокоенную женщинами, меньшинствами и студентами-инвалидами». [6]
В 1998 году в честь Лоулера был посвящён специальный выпуск журнала «Математическое программирование» (т. 82, вып. 1–2) . [8]
Премия имени Юджина Л. Лоулера имени ACM присуждается Ассоциацией вычислительной техники каждые два года за «гуманитарный вклад в области компьютерных наук и информатики». [16]