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

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

Год	Лауреаты	За что присуждена премия
1979	Ричард Карп	за классификацию многих важных NP-полных задач ^[1]
	Кеннет Аппель Вольфганг Хакен	за решение задачи четырёх красок ^[2]
	Пол Сеймур	за обобщение теоремы Форда — Фалкерсона на матроиды ^[3]
1982	Давид Юдин Аркадий Немировский Леонид Хачиян	за метод эллипсоидов в линейном программировании ^[4] ^[5]
	Георгий Егорычев Дмитрий Фаликман	за доказательство гипотезы ван дер Вардена о перманенте дважды стохастической матрицы ^[6]
	Мартин Грётшель Ласло Ловас Александр Схрейвер	за метод эллипсоидов в комбинаторной оптимизации ^[7]
1985	Йозеф Бек	за оценку границ расходимости целочисленных последовательностей ^[8]
	Хендрик Ленстра	за эффективный метод решения целочисленных программ с помощью геометрии чисел ^[9]
	Юджин Лукс	за полиномиальный алгоритм определения изоморфных графов ограниченной степени ^[10]
1988	Эва Тардош	за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложности ^[11]
1988	Нарендра Кармаркар	за алгоритм Кармаркара ^[12]
1991	Мартин Дайер Алан Фриз Равиндран Каннан	за блуждающий алгоритм оценки объёма выпуклых тел ^[13]
	Альфред Леман	за аналоги бинарных матриц в теории совершенных графов ^[14]
	Николай Мнёв	за теорему универсальности о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида ^[15]
1994	Луис Бильера	за нахождение базисов пространства частично-полиномиальных функций ^[16]
	Гиль Калай	за работу над гипотезой Хирша ^[17]
	Нейл Робертсон	за шестицветное решение гипотезы Хадвигера ^[18]
1997	Чон Хан Ким	за асимптотический анализ чисел Рамсея R(3,t) ^[19]
2000	Мишел Хуманс Дэвид Уильямсон	за алгоритмы аппроксимации в полуопределённом программировании ^[20]
2000	Мишель Конфорти Жерар Корнюэжоль Менду Рао	за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время ^[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)
2018	Томас Ротвосс	за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» (англ. The Matching Polytope has Exponential Extension Complexity)
2021	Бела Чаба Даниэла Кюн Аллан Ло Дерек Остус Эндрю Треглоу	за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях ^[38]
	Цай Цзинь Си Чэнь	за определение сложности вычисления статистических сумм ^[39]
	Кен-Ичи Каварабаяси Миккель Торуп	за разработку детерминированного алгоритма определения реберной связности ^[40]

Страница премии на сайте AMS Архивная копия от 15 марта 2010 на Wayback Machine
Страница премии на сайте MOS Архивная копия от 12 февраля 2019 на Wayback Machine
Список получавших премию на сайте AMS Архивная копия от 13 ноября 2013 на Wayback Machine

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

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

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

Примечания

Ссылки

Категории