Джек Эдмондс
Джек Эдмондс | |
|---|---|
 Эдмондс со своим камнем NP возле своего дома в Онтарио, Канада. | |
| Рожденный | Джон Роберт Эдмондс 5 апреля 1934 г. |
| Альма-матер | |
| Известный | |
| Награды | Премия Джона фон Неймана за теорию (1985) |
| Научная карьера | |
| Поля | Информатика, Математика |
| Учреждения | |
| Докторанты | |
Джек Р. Эдмондс родившийся в Америке и получивший образование, (родился 5 апреля 1934 г.) - ученый-компьютерщик и математик, большую часть своей жизни жил и работал в Канаде. Он внес фундаментальный вклад в области комбинаторной оптимизации , полиэдральной комбинаторики , дискретной математики и теории вычислений. Он был лауреатом Премии Джона фон Неймана в области теории 1985 года .
карьера Ранняя
Эдмондс учился в Технологической средней школе Мак-Кинли , которую окончил в 1952 году; [1] и рассказал о влиянии, которое эта школа оказала на его карьеру (например, на введении в галерею NIST в 2014 году). [2] [3] [4] ). Эдмондс учился в Университете Дьюка, а затем получил степень бакалавра в Университете Джорджа Вашингтона в 1957 году. После этого он получил степень магистра в 1960 году в Университете Мэриленда под руководством Брюса Л. Рейнхарта, защитив диссертацию по проблеме внедрения графов в поверхности. [5] [6] С 1959 по 1969 год он работал в Национальном институте стандартов и технологий (тогда Национальное бюро стандартов) и был одним из основателей недавно созданной секции исследования операций Алана Голдмана в 1961 году. Голдман оказал решающее влияние, предоставив возможность Эдмондс будет работать в мастерской, спонсируемой RAND Corporation, в Санта-Монике, Калифорния. Именно здесь Эдмондс впервые представил свои выводы по определению класса алгоритмов, которые могли бы работать более эффективно. Большинство ученых-комбинаториков в то время не занимались алгоритмами. Однако они привлекли Эдмондса, и эти первоначальные исследования стали ключевыми событиями для его более поздних работ между матроидами и оптимизацией. Он посвятил годы с 1961 по 1965 год изучению соотношения NP и P, а в 1966 году выдвинул гипотезы NP ≠ P и NP ∩ coNP = P.
Исследования [ править ]
Статья Эдмондса 1965 года «Пути, деревья и цветы» была выдающейся статьей, первоначально предполагавшей возможность создания математической теории эффективных комбинаторных алгоритмов. Одним из его первых и заметных достижений является алгоритм Блума для построения максимальных паросочетаний на графах, открытый в 1961 году. [7] и опубликовано в 1965 г. [8] Это был первый алгоритм с полиномиальным временем для максимального соответствия на графах. Его обобщение на взвешенные графы [9] стал концептуальным прорывом в использовании идей линейного программирования в комбинаторной оптимизации . В нем подчеркивается важность наличия доказательств или «свидетелей» того, что ответ для конкретного случая — «да», и наличия доказательств или «свидетелей» того, что ответ для конкретного случая — нет. В этой статье об алгоритме Блума Эдмондс также характеризует возможные проблемы как проблемы, решаемые за полиномиальное время; это одно из истоков тезиса Кобэма-Эдмондса . [10]
Прорывом в диссертации Кобэма-Эдмондса стало определение концепции полиномиального времени, характеризующего разницу между практическим и непрактичным алгоритмом (в современных терминах - разрешимой или неразрешимой проблемой). называются классом сложности PTIME или просто P. Сегодня задачи, решаемые за полиномиальное время ,
Статья Эдмондса «Максимальное паросочетание и многогранник с вершинами 0–1» вместе с его предыдущей работой предоставила удивительные алгоритмы с полиномиальным временем для построения максимальных паросочетаний. В частности, эти статьи продемонстрировали, как хорошая характеристика многогранника, связанного с проблемой комбинаторной оптимизации, может привести с помощью теории двойственности линейного программирования к построению эффективного алгоритма для решения этой проблемы.
Еще одна знаковая работа Эдмондса относится к области матроидов . Он нашел многогранное описание для всех остовных деревьев графа и, в более общем смысле, для всех независимых множеств матроида. [11] Основываясь на этом, как новом приложении линейного программирования к дискретной математике, он доказал теорему о пересечении матроидов , очень общую комбинаторную теорему о мин-максе. [12] [13] что, говоря современным языком, показало, что проблема пересечения матроидов лежит как в NP , так и в co-NP .
Эдмондс хорошо известен своими теоремами об алгоритмах ветвления с максимальным весом. [14] и упаковка разветвлений, не пересекающихся по краям [15] и его работа с Ричардом Карпом над алгоритмами более быстрого потока . Теорема о разложении Эдмондса –Галлаи описывает конечные графы с точки зрения паросочетаний. Он ввел полиматроиды , [12] субмодульные потоки с Ричардом Джайлсом, [16] а также термины «беспорядок» и «блокатор» при изучении гиперграфов . [7] Постоянная тема в его творчестве [17] заключается в поиске алгоритмов, временная сложность которых полиномиально ограничена размером входных данных и битовой сложностью. [7]
Карьера [ править ]
С 1969 года, за исключением 1991–1993 годов, он занимал должность преподавателя на кафедре комбинаторики и оптимизации Ватерлоо Университета математического факультета , где его исследования охватывали задачи комбинаторной оптимизации и связанные с ними многогранники. За это время он руководил докторской работой десятка студентов. Он читал курсы или проводил исследовательские отпуска в Университете Дьюка, Университете Джорджа Вашингтона, Университете Мэриленда,Стэнфорд, Принстон, Корнелл, а также университеты Китая, Левена (Бельгия), Копенгагена,Южная Дания (Оденсе), Париж, Марсель, Гренобль (Франция), а также Бонн и Кельн (Германия).
С 1991 по 1993 год он был вовлечен в спор («дело Эдмондса») с Университетом Ватерлоо. [18] [19] при этом университет утверждал, что представленное письмо представляет собой заявление об отставке, что Эдмондс отрицал. [20] Конфликт разрешился в 1993 году, и он вернулся в университет.
Эдмондс ушел из Университета Ватерлоо в 1999 году.
Награды и почести [ править ]
Эдмондс был лауреатом премии Джона фон Неймана в области теории в 1985 году .
как выдающаяся публикация В 2001 году его статья «Пути, деревья и цветы» была отмечена Национальным институтом стандартов и технологий в их праздничном издании «Столетие передового опыта в области стандартов и технологий измерений».
В 2002 году он был избран в класс научных сотрудников Института исследования операций и наук управления . [21]
В 2006 году королева Дании вручила Эдмондсу звание почетного доктора Университета Южной Дании .
В 2014 году он был удостоен звания «Заслуженный учёный» и зачислен в галерею Национального института стандартов и технологий.
пятый австралийский семинар по комбинаторной оптимизации в 2001 году. Ему был посвящен [13]
Личная жизнь [ править ]
Сын Джека Джефф Эдмондс — профессор информатики в Йоркском университете , а его жена Кэти Кэмерон — профессор математики в Университете Лорье .
См. также [ править ]
Ссылки [ править ]
- ^ https://www.dc-fifties.net/tech_1952_roster.html
- ^ https://www.nist.gov/system/files/documents/2017/05/09/Portrait-Gallery-Program-Brochure2014.pdf .
- ^ https://math.nist.gov/mcsd/Seminars/2014/2014-10-10-Edmonds.html .
- ^ https://math.nist.gov/mcsd/Seminars/2014/2014-10-10-Edmonds-presentation.pdf .
- ^ «Джек Эдмондс» . Проект «Математическая генеалогия» . Проверено 23 июня 2022 г.
- ^ Эдмондс-младший, Джон Роберт (1960). Комбинаторное представление ориентированных многогранных поверхностей . Проверено 23 июня 2022 г.
- ↑ Перейти обратно: Перейти обратно: а б с Эдмондс, Джек (1991), «Взгляд на небеса», в Дж. К. Ленстре; AHG Риннуй Кан; А. Шрийвер (ред.), История математического программирования - Сборник личных воспоминаний , CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.
- ^ Эдмондс, Джек (1965). «Дорожки, деревья и цветы» . Может. Дж. Математика . 17 : 449–467. дои : 10.4153/CJM-1965-045-4 . S2CID 247198603 .
- ^ Эдмондс, Джек (1965). «Максимальное паросочетание и многогранник с 0,1-вершинами» . Журнал исследований Национального бюро стандартов . Раздел B. 69 (1 и 2): 125–130. дои : 10.6028/jres.069B.013 .
- ^ Меран, Жерар (2014). Алгоритмы и сложность . п. п. 4 . ISBN 978-0-08093391-7 .
Задача считается выполнимой, если ее можно решить за полиномиальное время (как впервые было сказано Эдмондсом [26] [1965, «Пути, деревья и цветы]»).
- ^ Эдмондс, Джек (1971). «Матроиды и жадный алгоритм». Математика. Программирование (Принстонский симпозиум Math. Prog., 1967) . 1 : 127–136.
- ↑ Перейти обратно: Перейти обратно: а б Эдмондс, Джек (1970). «Субмодулярные функции, матроиды и некоторые многогранники». У Р. Гая; Х. Ханам; Н. Зауэр; Дж. Шонхайм (ред.). Комбинаторные структуры и их приложения (Труды конференции в Калгари, 1969 г.) . Гордон и Брич, Нью-Йорк. стр. 69–87. .
- ↑ Перейти обратно: Перейти обратно: а б Юнгер, Майкл; Рейнельт, Герхард; Ринальди, Джованни, ред. (2003), Комбинаторная оптимизация - Эврика, ты уменьшаешься! , Конспекты лекций по информатике, вып. 2570, Спрингер
- ^ Эдмондс, Джек (1967). «Оптимальные разветвления» . Журнал исследований Национального бюро стандартов . Раздел B. 71Б (4): 233–240. дои : 10.6028/jres.071B.032 .
- ^ Эдмондс, Джек (1973), Р. Растин (редактор), «Реберно-непересекающиеся разветвления», Комбинаторные алгоритмы | Симпозиум по информатике Куранта 9, 1972 , Монтерей, Калифорния, 1972: Algorithmics Press, Нью-Йорк: 91–96
{{citation}}: CS1 maint: местоположение ( ссылка ) - ^ Эдмондс, Джек; Джайлз, Ричард (1977), П. Л. Хаммер; Э. Л. Джонсон; Б. Х. Корте; Г. Л. Немхаузер (ред.), «Соотношение мин-макс для субмодулярных функций на графах», Исследования по целочисленному программированию | Труды семинара по целочисленному программированию, Бонн, 1975 , Annals of Discrete Mathematics, 1 , Северная Голландия, Амстердам: 185–204, doi : 10.1016/S0167-5060(08)70734-9 , ISBN 9780720407655
- ^ Кристоф Вицгалл (2001), «Пути, деревья и цветы», Век передового опыта в измерениях, стандартах и технологиях (PDF) , Национальный институт стандартов и технологий, стр. 140–144, заархивировано из оригинала (PDF) 25 марта 2006 г. , получено 11 августа 2011 г.
- ↑ UW Gazette, 7 октября 1992 г.: CAUT позвонил по делу Джека Эдмондса.
- ^ Введение редактора. Архивировано 27 октября 2010 г. в Wayback Machine , в: Кеннет Вестхьюс, изд., Моббинг на рабочем месте в академии: отчеты из двадцати университетов, Льюистон: Нью-Йорк: The Edwin Mellen Press, 2004.
- ↑ Ежедневный бюллетень Университета Ватерлоо, 5 марта 2001 г.: Конференция чествует Джека Эдмондса.
- ^ Стипендиаты: Алфавитный список , Институт исследования операций и наук управления , заархивировано из оригинала 10 мая 2019 г. , получено 9 октября 2019 г.
Внешние ссылки [ править ]
- Джек Эдмондс в проекте «Математическая генеалогия»
- Биография Джека Эдмондса из Института исследования операций и наук управления
