Джек Эдмондс - Jack Edmonds

Джек Эдмондс
Jack.Edmonds.jpg
Эдмондс со своей скалой NP у своего дома в Онтарио, Канада
Родившийся
Джон Роберт Эдмондс

(1934-04-05) 5 апреля 1934 г. (86 лет)
Вашингтон, округ Колумбия.
Альма-матерУниверситет Мэриленда
Университет Джорджа Вашингтона
Университет Дьюка
ИзвестенНП
Алгоритм Эдмондса – Карпа
Теорема Эдмондса – Галлаи о разложении
Тезис Кобэма
Алгоритм цветения
Алгоритм Эдмондса
Полиматроид
Пересечение матроидов
Матрица Эдмондса
НаградыПремия Джона фон Неймана по теории (1985)
Научная карьера
ПоляКомпьютерные науки, математика
УчрежденияУниверситет Ватерлоо
Национальный институт стандартов и технологий
ДокторантыПейтон Янг
Уильям Р. Пуллибланк
Жилберто Кальвилло Вивес
Мустафа Акгуль
Арнальдо Мандель
Ефрем Корах
Том Дженкинс
Виктор Гриффин
Рик Джайлз
Кэти Кэмерон
Комей Фукуда
Уильям Каннингем
Джулиан Араоз Дюран

Джек Р. Эдмондс (родился 5 апреля 1934 г.), родился в США и получил образование. специалист в области информатики и математик который большую часть своей жизни жил и работал в Канаде. Он внес фундаментальный вклад в области комбинаторная оптимизация, многогранная комбинаторика, дискретная математика и теория вычислений. Он был лауреатом Премии Джона фон Неймана 1985 года.

Ранняя карьера

Эдмондс учился в Университете Дьюка, а затем получил степень бакалавра в Университете Джорджа Вашингтона в 1957 году. После этого он учился в аспирантуре Мэрилендского университета, защитив диссертацию по проблеме вложения графов в поверхности. С 1959 по 1969 год работал в Национальный институт стандартов и технологий (затем Национальное бюро стандартов), и был одним из основателей Алан Гольдман Недавно созданный Отдел исследования операций в 1961 году. Голдман оказал решающее влияние, позволив Эдмондсу работать в мастерской, спонсируемой RAND Corporation, в Санта-Монике, Калифорния. Именно здесь Эдмондс впервые представил свои выводы по определению класса алгоритмов, которые могли бы работать более эффективно. Большинство исследователей комбинаторики в то время не занимались алгоритмами. Однако Эдмондс был привлечен к ним, и эти первоначальные исследования были ключевыми достижениями для его более поздней работы между матроидами и оптимизацией. Он потратил годы с 1961 по 1965 на тему сравнения NP и P, а в 1966 году выдвинул гипотезы NP ≠ P и NP ∩ coNP = P.

Исследование

Статья Эдмондса 1965 года «Пути, деревья и цветы» была выдающейся статьей, изначально предлагавшей возможность создания математической теории эффективных комбинаторных алгоритмов. Одним из его самых ранних и заметных вкладов является алгоритм цветения для строительства максимальное соответствие на графиках, обнаруженных в 1961 г.[1] и опубликовано в 1965 году.[2] Это был первый алгоритм с полиномиальным временем для максимального соответствия в графах. Его обобщение на взвешенные графы[3] был концептуальным прорывом в использовании линейное программирование идеи в комбинаторная оптимизация. Он подтвердил важность наличия доказательств или «свидетелей», что ответ для примера - да, и наличия доказательств, или «свидетелей», что ответ для примера - нет. В этой статье об алгоритме цветения Эдмондс также характеризует возможные проблемы как решаемые за полиномиальное время; это одно из истоков Тезис Кобэма – Эдмондса.[4]

Прорыв Тезис Кобэма – Эдмондса, определяла понятие полиномиального времени, характеризующего разницу между практичным и непрактичным алгоритмом (в современных терминах, разрешимая проблема или неразрешимая проблема). Сегодня задачи, решаемые за полиномиальное время, называют класс сложности PTIME, или просто п.

Статья Эдмонда «Максимальное сопоставление и многогранник с вершинами 0–1» вместе с его предыдущей работой дали удивительные алгоритмы с полиномиальным временем для построения максимального сопоставления. В частности, эти статьи продемонстрировали, как хорошая характеристика многогранника, связанного с задачей комбинаторной оптимизации, может привести с помощью теории двойственности линейного программирования к построению эффективного алгоритма для решения этой проблемы.

Дополнительные знаковые работы Эдмондса находятся в районе матроиды. Он нашел многогранное описание для всех остовные деревья графа и вообще для всех независимых наборов матроида.[5] Основываясь на этом, как на новом приложении линейного программирования к дискретной математике, он доказал, что пересечение матроидов теорема, очень общая комбинаторная теорема мин-макс[6][7] что, говоря современным языком, показало, что проблема пересечения матроидов лежит в обоих НП и со-НП.

Эдмондс хорошо известен своими теоремами о алгоритмы ветвления с максимальным весом[8] и упаковка непересекающихся разветвлений[9] и его работа с Ричард Карп на более быстрые алгоритмы потока. В Теорема Эдмондса – Галлаи о разложении описывает конечные графы с точки зрения паросочетаний. Он представил полиматроиды,[6] субмодульный течет с Ричардом Джайлсом,[10] и условия беспорядок и блокиратор при изучении гиперграфы.[1] Постоянная тема в его творчестве[11] заключается в поиске алгоритмов, временная сложность которых полиномиально ограничена их размером ввода и битовой сложностью.[1]

Карьера

С 1969 г., за исключением 1991–1993 гг., Он занимал должность преподавателя на кафедре комбинаторики и оптимизации ФГБНУ им. Университет Ватерлоо с Факультет математики где его исследования охватывали задачи комбинаторной оптимизации и связанные с ними многогранники. За это время он руководил докторской работой десятка студентов.

С 1991 по 1993 год он участвовал в споре («дело Эдмондса») с Университетом Ватерлоо,[12][13] при этом университет утверждал, что представленное письмо представляет собой заявление об увольнении, которое Эдмондс отрицал.[14] Конфликт разрешился в 1993 году, и он вернулся в университет.

Эдмондс ушел из Университета Ватерлоо в 1999 году.

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

Эдмондс был удостоен награды 1985 г. Премия Джона фон Неймана по теории.

В 2001 году его статья «Путь, деревья и цветы» была отмечена как выдающееся издание Национальный институт стандартов и технологий в своем праздничном выпуске «Век передового опыта в области стандартов и технологий измерений»

Был избран в класс 2002 г. Стипендиаты из Институт исследований операций и управленческих наук.[15]

В 2006 году королева Дании вручила Эдмондсу степень почетного доктора Университет Южной Дании.

В 2014 году он был удостоен звания Заслуженного ученого и принят в Галерею Национального института стандартов и технологий.

Пятый Aussois Ему был посвящен семинар по комбинаторной оптимизации 2001 года.[7]

Личная жизнь

Сын Джека Джефф Эдмондс профессор информатики в Йоркский университет, а его жена Кэти Кэмерон - профессор математики в Университет Лорье.

Смотрите также

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

  1. ^ а б c Эдмондс, Джек (1991), «Взгляд на небеса», в J.K. Ленстра; A.H.G. Риннуй Кан; А. Шрайвер (ред.), История математического программирования - сборник личных воспоминаний, CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.
  2. ^ Эдмондс, Джек (1965). «Дорожки, деревья и цветы». Может. J. Math. 17: 449–467. Дои:10.4153 / CJM-1965-045-4.
  3. ^ Эдмондс, Джек (1965). «Максимальное соответствие и многогранник с 0,1-вершиной». Журнал исследований Национального бюро стандартов Раздел B. 69: 125–130.
  4. ^ Меурант, Жерар (2014). Алгоритмы и сложность. п.п. 4. ISBN  978-0-08093391-7. Говорят, что проблема достижимый если ее можно решить за полиномиальное время (как впервые было заявлено Эдмондсом [26] [1965, Пути, деревья и цветы])).
  5. ^ Эдмондс, Джек (1971). «Матроиды и жадный алгоритм». Математика. Программирование (Princeton Symposium Math. Prog. 1967). 1: 127–136.
  6. ^ а б Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», у Р. Гая; Х. Ханам; Н. Зауэр; J. Schonheim (ред.), Комбинаторные структуры и их приложения (Proc. 1969 Calgary Conference), Гордон и Брич, Нью-Йорк, стр. 69–87..
  7. ^ а б Юнгер, Михаэль; Райнельт, Герхард; Ринальди, Джованни, ред. (2003), «Комбинаторная оптимизация - Эврика, вы сжимаетесь!», Конспект лекций по информатике, Спрингер, 2570
  8. ^ Эдмондс, Джек (1967). «Оптимальные разветвления». J. Res. Nat. Бур. Стандарты. 71B: 233–240.
  9. ^ Эдмондс, Джек (1973), Р. Растин (редактор), "Реберно-непересекающиеся ветвления", Комбинаторные алгоритмы, Монтерей, Калифорния, 1972: Algorithmics Press, Нью-Йорк: 91–96.CS1 maint: location (связь)
  10. ^ Эдмондс, Джек; Джайлз, Ричард (1977), П. Молоток; E.L. Джонсон; B.H. Корте; Г.Л. Немхаузер (ред.), "Отношение min-max для субмодулярных функций на графах", Исследования в области целочисленного программирования, Анналы дискретной математики, Северная Голландия, Амстердам, 1: 185–204
  11. ^ Кристоф Витцгалл (2001), «Дорожки, деревья и цветы», Век передового опыта в измерениях, стандартах и ​​технологиях (PDF), Национальный институт стандартов и технологий, стр. 140–144, архивировано с оригинал (PDF) на 2006-03-25, получено 2011-08-11
  12. ^ UW Gazette, 7 октября 1992 г .: Компания CAUT обратилась к делу Джека Эдмондса.
  13. ^ Введение редактора В архиве 2010-10-27 на Wayback Machine, in: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004.
  14. ^ Ежедневный бюллетень Университета Ватерлоо, 5 марта 2001 г .: Конференция чтит Джека Эдмондса
  15. ^ Стипендиаты: Алфавитный список, Институт исследований операций и управленческих наук, заархивировано из оригинал на 2019-05-10, получено 2019-10-09

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