Премия Фалкерсона

Премия Фалкерсона — научная награда за выдающиеся работы в области дискретной математики, вручаемая совместно Обществом математической оптимизации^[англ.] (MOS) и Американским математическим обществом (AMS) на международном симпозиуме MOS, который проходит раз в три года. На каждом таком мероприятии объявляется более трёх номинаций, каждая из которых может включать нескольких учёных. Размер премии — полторы тысячи долларов, изначально выплачивалась из фонда, организованного друзьями Делберта Рея Фалкерсона после его смерти для поддержки математических работ в его области.

Лауреаты премии

Год	Лауреаты	За что присуждена премия
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	Бен Кузен[англ.] Сантош Вемпала[англ.]	за технику гауссова охлаждения и ${\displaystyle O^{*}(n^{3})}$-алгоритмы вычисления объёма и гауссова объёма
	Цзылинь Цзян Джонатан Тайдор Юань Яо Шэнтун Чжан Юйфэй Чжао	за работу по равноугольным прямым под заданным уголом
	Натан Келлер Ноам Лифшиц	за метод хунты для гипеграфов и решение симплектической гипотезы Эрдёша — Хватала[41]