Год |
Лауреаты |
За что присуждена премия |
1979 |
Ричард Карп |
за классификацию многих важных NP-полных задач[1] |
Кеннет Аппель[англ.] Вольфганг Хакен |
за решение задачи четырёх красок[2] |
Пол Сеймур |
за обобщение теоремы Форда — Фалкерсона на матроиды[3] |
1982 |
Давид Юдин Аркадий Немировский Леонид Хачиян |
за метод эллипсоидов в линейном программировании[4][5] |
Георгий Егорычев[англ.] Дмитрий Фаликман |
за доказательство гипотезы ван дер Вардена о перманенте дважды стохастической матрицы[6] |
Мартин Грётшель[нем.] Ласло Ловас Александр Схрейвер |
за метод эллипсоидов в комбинаторной оптимизации[7] |
1985 |
Йозеф Бек[англ.] |
за оценку границ расходимости целочисленных последовательностей[8] |
Хендрик Ленстра |
за эффективный метод решения целочисленных программ с помощью геометрии чисел[9] |
Юджин Лукс[англ.] |
за полиномиальный алгоритм определения изоморфных графов ограниченной степени[10] |
1988 |
Эва Тардош |
за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложности[11] |
Нарендра Кармаркар |
за алгоритм Кармаркара[12] |
1991 |
Мартин Дайер[англ.] Алан Фриз[англ.] Равиндран Каннан |
за блуждающий алгоритм оценки объёма выпуклых тел[13] |
Альфред Леман |
за аналоги бинарных матриц в теории совершенных графов[14] |
Николай Мнёв[араб. егип.] |
за теорему универсальности[англ.] о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида[15] |
1994 |
Луис Бильера[англ.] |
за нахождение базисов пространства частично-полиномиальных функций[16] |
Гиль Калай[англ.] |
за работу над гипотезой Хирша[17] |
Нейл Робертсон[англ.] |
за шестицветное решение гипотезы Хадвигера[18] |
1997 |
Чон Хан Ким[англ.] |
за асимптотический анализ чисел Рамсея R(3,t)[19] |
2000 |
Мишел Хуманс[англ.] Дэвид Уильямсон[англ.] |
за алгоритмы аппроксимации в полуопределённом программировании[20] |
Мишель Конфорти[нем.] Жерар Корнюэжоль[нем.] Менду Рао[англ.] |
за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время[21] |
2003 |
Джеймс Гейлен[англ.] Берт Герардс Аджай Капур |
за GF(4)-решение гипотезы Роты[англ.] для матроидных миноров[англ.][22] |
Бертран Гьюнин |
за характеризацию запрещённых миноров слабо двудольных графов[23] |
Сатору Ивата Лиза Фляйшер Сатору Фудзисигэ Лекс Схрейвер |
за доказательство сильной полиномиальности субмодулярной минимизации[24][25] |
2006 |
Маниндра Агравал[англ.] Нирадж Каял[англ.] Нитин Саксена[англ.] |
за тест Агравала — Каяла — Саксены[26] |
Марк Еррум[англ.] Алистер Синклер[англ.] Эрик Вигода |
за аппроксимацию перманента[27] |
Нейл Робертсон[англ.] Пол Сеймур |
за теорему Робертсона — Сеймура[28] |
2009 |
Мария Чудновская[англ.] Нейл Робертсон[англ.] Пол Сеймур Робин Томас |
за теорему о сильно идеальных графах[29] |
Дэниэл Спилмен Тэн Шанхуа |
за сглаженный анализ[англ.] алгоритмов линейного программирования[30][31] |
Томас Хейлс[англ.] Самуэль Фергюсон[нем.] |
за доказательство гипотезы Кеплера для самой плотной упаковки шаров[32][33] |
2012 |
Санджив Арора Сатиш Рао[англ.] Умеш Вазирани |
за снижение сложности алгоритма аппроксимации разделителей графов[34] |
Андерс Йохансон Джефф Кан[англ.] Ву Ха Ван |
за определение границы плотности дуг, с которой случайный граф может быть покрыт непересекающимися копиями данного меньшего графа[35] |
Ласло Ловас Балаш Сегеди[англ.] |
за оценку кратности подграфов в последовательностях плотных графов[36] |
2015 |
Франсиско Сантос |
за контрпример к гипотезе Хирша[37] |
2018 |
Питер Аллен Юлия Бёттхер Саймон Гриффитс Ёсихару Кохаякава[англ.] Роберт Моррис[англ.] |
за работу «Хроматические пороги графов» (англ. The chromatic thresholds of graphs) |
Томас Ротвосс[нем.] |
за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» (англ. The Matching Polytope has Exponential Extension Complexity) |
2021 |
Бела Чаба Даниэла Кюн[англ.] Аллан Ло Дерек Остус[англ.] Эндрю Треглоу |
за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях[38] |
Цай Цзинь[англ.] Си Чэнь |
за определение сложности вычисления статистических сумм[39] |
Кен-Ити Каварабаяси[англ.] Миккель Торуп[англ.] |
за разработку детерминированного алгоритма определения рёберной связности[40] |
2024 |
Бен Кузен[англ.] Сантош Вемпала[англ.] |
за технику гауссова охлаждения и -алгоритмы вычисления объёма и гауссова объёма |
Цзылинь Цзян Джонатан Тайдор Юань Яо Шэнтун Чжан Юйфэй Чжао |
за работу по равноугольным прямым под заданным уголом |
Натан Келлер Ноам Лифшиц |
за метод хунты для гипеграфов и решение симплектической гипотезы Эрдёша — Хватала[41] |