Войти
| Джек Эдмондс | |
|---|---|
 Эдмондс со своей скалой NP возле своего дома в Онтарио, Канада | |
| Родился | Джон Роберт Эдмондс. (1934-04-05) 5 апреля 1934 (возраст 86). Вашингтон, округ Колумбия |
| Alma mater | Университет штата Мэриленд. Университет Джорджа Вашингтона. Университет Дьюка |
| Известен благодаря | NP. алгоритму Эдмондса – Карпа. Теорема разложения Эдмондса – Галлая. Тезис Кобхэма. Алгоритм Блоссома. алгоритм Эдмондса. Полиматроид. Пересечение матроидов. Матрица Эдмондса |
| Награды | Теоретическая премия Джона фон Неймана (1985) |
| Научная карьера | |
| Области | Компьютерные науки, математика |
| Учреждения | Университет Ватерлоо. Национальный институт стандартов и технологий |
| Докторанты | Пейтон Янг. Уильям Р. Пуллибланк. Жилберто Кальвилло Вивес. Мустафа Акгул. Арнальдо Мандель. Эфраим Корах. Том Дженкинс. Виктор Гриффин. Рик Джайлс. Кэти Кэмерон. Комей Фукуда. Уильям Каннингем. Джулиан Араоз Дюран |
Джек Р. Эдмондс (родился 5 апреля 1934 г.) - американец, получивший образование компьютерный ученый и математик который большую часть своей жизни жил и работал в Канаде. Он внес фундаментальный вклад в области комбинаторной оптимизации, полиэдральной комбинаторики, дискретной математики и теории вычислений. Он был лауреатом Премии Джона фон Неймана 1985 года.
Эдмондс учился в Университете Дьюка, прежде чем в 1957 году получил степень бакалавра в Университете Джорджа Вашингтона. После этого он продолжил обучение в аспирантуре Университета Мэриленда, защитив диссертацию по проблеме вложения графов в поверхности. С 1959 по 1969 год он работал в Национальном институте стандартов и технологий (затем Национальное бюро стандартов) и был одним из основателей недавно созданной Секции исследования операций Алана Голдмана. в 1961 году. Голдман оказал решающее влияние, позволив Эдмондсу работать в мастерской, спонсируемой RAND Corporation, в Санта-Монике, Калифорния. Именно здесь Эдмондс впервые представил свои выводы по определению класса алгоритмов, которые могли бы работать более эффективно. Большинство исследователей комбинаторики в то время не занимались алгоритмами. Однако Эдмондс был привлечен к ним, и эти первоначальные исследования стали ключевыми событиями для его более поздней работы между матроидами и оптимизацией. Он потратил годы с 1961 по 1965 на тему сравнения NP и P, а в 1966 году выдвинул гипотезы NP ≠ P и NP ∩ coNP = P.
Статья Эдмондса 1965 года «Пути, Деревья и цветы »была выдающейся статьей, изначально предлагавшей возможность создания математической теории эффективных комбинаторных алгоритмов. Одним из его самых ранних и заметных вкладов является алгоритм цветения для построения максимального соответствия на графах, открытый в 1961 году и опубликованный в 1965 году. Это был первый алгоритм с полиномиальным временем для максимального соответствия в графики. Его обобщение на взвешенные графы стало концептуальным прорывом в использовании идей линейного программирования в комбинаторной оптимизации. Он подтвердил важность наличия доказательств или «свидетелей», что ответ для примера - да, и наличия доказательств, или «свидетелей», что ответ для примера - нет. В этой статье об алгоритме цветения Эдмондс также характеризует возможные проблемы как решаемые за полиномиальное время; это одно из истоков тезиса Кобэма-Эдмондса.
Прорывом тезиса Кобэма-Эдмондса было определение концепции полиномиального времени, характеризующей разницу между практичным и непрактичным алгоритмом (говоря современным языком, решаемая проблема или неразрешимая проблема). Сегодня задачи, решаемые за полиномиальное время, называются классом сложности PTIME, или просто P.
статьей Эдмонда «Максимальное соответствие и многогранник с 0-1 вершинами» вместе с его предыдущей работой. дал удивительные полиномиальные алгоритмы построения максимальных сопоставлений. В частности, эти статьи продемонстрировали, как хорошая характеристика многогранника, связанного с задачей комбинаторной оптимизации, может привести с помощью теории двойственности линейного программирования к построению эффективного алгоритма для решения этой проблемы.
Дополнительная знаковая работа Эдмондса находится в области матроидов. Он нашел полиэдральное описание для всех остовных деревьев графа и, в более общем смысле, для всех независимых множеств матроида. Основываясь на этом, как на новом приложении линейного программирования к дискретной математике, он доказал теорему о пересечении матроидов, очень общую комбинаторную теорему о минимуме и максимуме, которая, говоря современным языком, показала, что проблема пересечения матроидов лежит в оба NP и co-NP.
Эдмондс хорошо известен своими теоремами о алгоритмах ветвления с максимальным весом и упаковкой непересекающихся по ребрам ветвлений, а также своей работой с Ричард Карп о алгоритмах ускоренного потока. Теорема Эдмондса – Галлаи о разложении описывает конечные графы с точки зрения паросочетаний. Он представил полиматроиды, субмодульные потоки с Ричардом Джайлсом, а также термины беспорядок и блокатор при изучении гиперграфов. Постоянной темой в его работе является поиск алгоритмов, временная сложность которых полиномиально ограничена их размером ввода и битовой сложностью.
Начиная с 1969 г., за исключением 1991–1993 гг. он работал преподавателем на кафедре комбинаторики и оптимизации на математическом факультете Университета Ватерлоо , где его исследования охватывали задачи комбинаторной оптимизации и связанные с ними многогранники. За это время он руководил докторской работой десятка студентов.
С 1991 по 1993 год он участвовал в споре («дело Эдмондса») с Университетом Ватерлоо, в котором университет утверждал, что представленное письмо представляет собой заявление об увольнении, которое Эдмондс отрицал. Конфликт разрешился в 1993 году, и он вернулся в университет.
Эдмондс ушел на пенсию из Университета Ватерлоо в 1999 году.
Эдмондс был лауреатом в 1985 году Премии Джона фон Неймана за теорию.
В В 2001 году его статья «Путь, деревья и цветы» была отмечена как выдающаяся публикация Национальным институтом стандартов и технологий в их праздничном выпуске «Век передового опыта в стандартах и технологиях измерений
<83.>Он был избран в 2002 году в класс стипендиатов Института исследований операций и управленческих наук.В 2006 году королева Дании вручила Эдмондсу степень почетного доктора Университета . Южной Дании.
В 2014 году он был удостоен звания выдающегося ученого и включен в галерею Национального института стандартов и технологий.
Пятый Осуа Семинар по комбинаторной оптимизации в 2001 году был посвящен ему.
Сын Джека Джефф Эдмондс является профессором информатики в Йоркском университете, а его жена Кэти Кэмерон - профессор математики в университете Лорье.
