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

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

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

Ранняя карьера [ править ]

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

Исследование [ править ]

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

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

Статья Эдмонда «Максимальное сопоставление и многогранник с вершинами 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 году он был удостоен звания заслуженного ученого и был принят в Галерею Национального института стандартов и технологий.

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

Личная жизнь [ править ]

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

См. Также [ править ]

  • Матрица Эдмондса

Ссылки [ править ]

  1. ^ a b c Эдмондс, Джек (1991), «Взгляд на небеса», в JK Lenstra; AHG Rinnooy Kan; А. Шрайвер (ред.), История математического программирования - Сборник личных воспоминаний , CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.
  2. ^ Эдмондс, Джек (1965). «Дорожки, деревья и цветы». Может. J. Math . 17 : 449–467. DOI : 10,4153 / CJM-1965-045-4 .
  3. ^ Эдмондс, Джек (1965). «Максимальное соответствие и многогранник с 0,1-вершиной». Журнал исследований Национального бюро стандартов Раздел B . 69 : 125–130.
  4. ^ Meurant, Gerard (2014). Алгоритмы и сложность . п. п. 4 . ISBN 978-0-08093391-7. Проблема называется выполнимой, если она может быть решена за полиномиальное время (как впервые было заявлено в Эдмондсе [26] [1965, Пути, деревья и цветы]).
  5. ^ Эдмондс, Джек (1971). «Матроиды и жадный алгоритм». Математика. Программирование (Princeton Symposium Math. Prog. 1967) . 1 : 127–136.
  6. ^ a b Эдмондс, Джек (1970), «Субмодульные функции, матроиды и некоторые многогранники», в R. Guy; Х. Ханам; Н. Зауэр; J. Schonheim (ред.), Комбинаторные структуры и их приложения (Proc. 1969 Calgary Conference) , Gordon and Breach, New York, pp. 69–87..
  7. ^ a b Юнгер, Майкл; Райнельт, Герхард; Ринальди, Джованни, ред. (2003), «Комбинаторная оптимизация - Эврика, сжимайся!», Лекционные заметки по информатике , Springer, 2570
  8. ^ Эдмондс, Джек (1967). «Оптимальные разветвления». J. Res. Nat. Бур. Стандарты . 71B : 233–240.
  9. ^ Эдмондс, Джек (1973), Р. Растин (ред.), "Edge-непересекающиеся ветвления", Combinatorial Algorithms , Монтерей, Калифорния, 1972: Algorithmics Press, Нью-Йорк: 91–96CS1 maint: location ( ссылка )
  10. ^ Эдмондс, Джек; Джайлз, Ричард (1977), П. Л. Хаммер; Э.Л. Джонсон; BH Korte; Г. Л. Немхаузер (ред.), «Отношение минимум-максимум для субмодульных функций на графах», Исследования по целочисленному программированию , Анналы дискретной математики, Северная Голландия, Амстердам, 1 : 185–204
  11. ^ Christoph Witzgall (2001), «Путь, дерева и цветы», Век передовых технологий в области измерений, стандарты и технологии (PDF) , Национальный институт стандартов и технологии, стр. 140-144, архивируется с оригинала (PDF ) 25 марта 2006 г. , дата обращения 11.08.2011.
  12. ^ UW Gazette, 7 октября 1992: Предостережение заехал на случай Джек Эдмондс
  13. ^ Введение редактора Архивировано 27 октября 2010 г.в Wayback Machine , в: Kenneth Westhues, ed., Workplace Mobbing in Academe: Reports from Twenty Universities, Lewiston: NY: The Edwin Mellen Press, 2004
  14. ^ Ежедневный бюллетень Университета Ватерлоо, 5 марта 2001: Конференция чтит Джека Эдмондса
  15. ^ Fellows: Alphabetical List , Institute for Operations Research and the Management Sciences , заархивировано из оригинала на 2019-05-10 , извлечено 2019-10-09.

Внешние ссылки [ править ]

  • Джек Эдмондс на проекте « Математическая генеалогия»
  • Биография Джека Эдмондса из Института исследований операций и наук управления