Джек Р. Эдмондс (родился 5 апреля 1934 года) — американский учёный- компьютерщик и математик , большую часть жизни проживший и работавший в Канаде. Он внёс фундаментальный вклад в области комбинаторной оптимизации , полиэдральной комбинаторики , дискретной математики и теории вычислений. В 1985 году он был удостоен премии Джона фон Неймана по теории .
Эдмондс учился в McKinley Technology High School , которую окончил в 1952 году; [1] и рассказывал о влиянии этой школы на его карьеру (например, на его представлении в галерее NIST в 2014 году [2] [3] [4] ). Эдмондс учился в Университете Дьюка, прежде чем получить степень бакалавра в Университете Джорджа Вашингтона в 1957 году. После этого он получил степень магистра в 1960 году в Университете Мэриленда под руководством Брюса Л. Рейнхарта, защитив диссертацию по проблеме встраивания графов в поверхности. [5] [6] С 1959 по 1969 год он работал в Национальном институте стандартов и технологий (тогда Национальное бюро стандартов) и был одним из основателей недавно созданного Аланом Голдманом Секции исследования операций в 1961 году. Голдман оказал решающее влияние, предоставив Эдмондсу возможность работать в спонсируемой корпорацией RAND мастерской в Санта-Монике, штат Калифорния. Именно здесь Эдмондс впервые представил свои выводы по определению класса алгоритмов, которые могли бы работать более эффективно. Большинство ученых-комбинаториков в то время не были сосредоточены на алгоритмах. Однако Эдмондс был привлечен к ним, и эти первоначальные исследования стали ключевыми разработками для его более поздних работ между матроидами и оптимизацией. Он провел годы с 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 году ему было присвоено звание «Выдающийся ученый», а его имя было включено в Галерею Национального института стандартов и технологий.
Пятый семинар Aussois по комбинаторной оптимизации в 2001 году был посвящен ему. [13]
Сын Джека Джефф Эдмондс — профессор компьютерных наук в Йоркском университете , а его жена Кэти Кэмерон — профессор математики в Университете Лорье .
Задача считается выполнимой, если ее можно решить за полиномиальное время (как впервые было заявлено в работе Эдмондса [26] [1965, Paths, trees, and flowers]).
{{citation}}: CS1 maint: местоположение ( ссылка )