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

Премия за достижения в области дискретной математики

Премия

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

Победители

• 1979 год:
  • Ричарду М. Карпу за классификацию многих важных NP-полных задач. ^[1]
  • Кеннет Аппель и Вольфганг Хакен за теорему о четырех цветах . ^[2]
  • Полу Сеймуру за обобщение теоремы о максимальном потоке и минимальном разрезе на матроиды . ^[3]
• 1982:
  • Д.Б. Юдину, Аркадию Немировскому , Леониду Хачияну , Мартину Гретшелю , Ласло Ловасу и Александру Шрийверу за метод эллипсоидов в линейном программировании и комбинаторной оптимизации . ^{[4] [5] [6] [7]}
  • Г. П. Егорычеву и Д. И. Фаликману за доказательство гипотезы ван дер Вардена о том, что матрица, у которой все элементы равны, имеет наименьший перманент из любой дважды стохастической матрицы . ^{[8] [9]}
• 1985:
  • Йожефа Бека за точные оценки неточности арифметических прогрессий . ^[10]
  • Х. В. Ленстра-младший за использование геометрии чисел для решения целочисленных программ с небольшим количеством переменных за полиномиальное по числу ограничений время. ^[11]
  • Юджин М. Лукс за полиномиальный алгоритм изоморфизма графов для графов ограниченной максимальной степени . ^{[12] [13]}
• 1988 год:
  • Эва Тардос за нахождение минимальных оборотов стоимости за сильно полиномиальное время . ^[14]
  • Нарендра Кармаркар за алгоритм Кармаркара для линейного программирования . ^[15]
• 1991 год:
  • Мартин Э. Дайер , Алан М. Фриз и Равиндран Каннан за алгоритмы аппроксимации объема выпуклых тел, основанные на случайном блуждании . ^[16]
  • Альфред Леман за 0,1-матричные аналоги теории совершенных графов . ^[17]
  • Мневу Николаю Евгеньевичу за теорему Мнева об универсальности о том, что каждое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида . ^[18]
• 1994:
  • Луи Биллера за нахождение баз кусочно-полиномиальных функциональных пространств над триангуляциями пространства. ^[19]
  • Гил Калаи за развитие гипотезы Хирша путем доказательства субэкспоненциальных оценок диаметра d -мерных многогранников с n гранями. ^[20]
  • Нил Робертсон , Пол Сеймур и Робин Томас за шестицветный случай гипотезы Хадвигера . ^[21]
• 1997:
  • Чон Хан Киму за нахождение асимптотической скорости роста чисел Рамсея R (3, t ). ^[22]
• 2000:
  • Мишель X. Гоеманс и Дэвид П. Уильямсон за алгоритмы аппроксимации, основанные на полуопределенном программировании . ^[23]
  • Мишель Конфорти, Жерар Корнюжоль и М.Р. Рао за распознавание сбалансированных матриц 0–1 за полиномиальное время . ^{[24] [25]}
• 2003:
  • Дж. Ф. Гилен , А. М. Джерардс и А. Капур за случай GF (4) гипотезы Роты о матроидных минорах . ^{[26] [27]}
  • Бертрану Генену за запрещенную второстепенную характеристику слабо двудольных графов (графов, многогранник двудольного подграфа которых равен 0–1). ^{[28] [27]}
  • Сатору Ивата, Лиза Фляйшер, Сатору Фудзисигэ и Александр Шрийвер за демонстрацию строгой полиномиальности субмодульной минимизации . ^{[29] [30] [27]}
• 2006:
  • Маниндра Агравал , Нирадж Каял и Нитин Саксена за тест на простоту AKS . ^{[31] [32] [33]}
  • Марку Джерруму , Алистеру Синклеру и Эрику Вигоде за приближение к перманенту . ^{[34] [33]}
  • Нилу Робертсону и Полу Сеймуру за теорему Робертсона-Сеймура, показывающую, что миноры графа образуют хорошо квазиупорядоченный объект . ^{[35] [33]}
• 2009:
  • Мария Чудновская , Нил Робертсон, Пол Сеймур и Робин Томас — за теорему о сильном совершенном графике . ^{[36] [37]}
  • Дэниелу А. Спилману и Шан-Хуа Тэну — за сглаженный анализ алгоритмов линейного программирования . ^{[38] [37]}
  • Томас К. Хейлз и Сэмюэл П. Фергюсон — за доказательство гипотезы Кеплера о максимально плотных упаковках сфер . ^{[39] [40] [37]}
• 2012:
  • Санджив Арора , Сатиш Рао и Умеш Вазирани за улучшение коэффициента аппроксимации для разделителей графов и связанных с ними задач от до . ^[41] ${\displaystyle O(\log n)}$ ${\displaystyle O({\sqrt {\log n}})}$
  • Андерсу Йоханссону, Джеффу Кану и Ван Х. Ву за определение порога плотности ребер, выше которого случайный граф может быть покрыт непересекающимися копиями заданного меньшего графа. ^[42]
  • Ласло Ловашу и Балашу Сегеди за характеристику кратности подграфов в последовательностях плотных графов . ^[43]
• 2015:
  • Франсиско Сантосу Леалю за контрпример к гипотезе Хирша . ^{[44] [45]}
• 2018:
  • Роберт Моррис , Ёсихару Кохаякава , Саймон Гриффитс, Питер Аллен и Джулия Бетчер за «Хроматические пороги графов».
  • Томас Ротвосс за работу по расширению сложности соответствующего многогранника . ^[46]
• 2021:
  • Бела Чаба, Даниэла Кюн , Аллан Ло, Дерик Остус и Эндрю Треглоун за доказательство гипотез 1-факторизации и разложения Гамильтона.
  • Цзинь-И Цай и Си Чен о сложности подсчета CSP с комплексными весами
  • Кен-Ичи Каварабаяши и Миккель Торуп за детерминированную граничную связность в почти линейном времени

Источник: официальный сайт Общества математической оптимизации. ^[47]

Смотрите также

• Список наград по математике

Рекомендации

1. Карп, Ричард М. (1975). «О вычислительной сложности комбинаторных задач». Сети . 5 : 45–68. дои : 10.1002/net.1975.5.1.45.
2. Аппель, Кеннет ; Хакен, Вольфганг (1977). «Каждая планарная карта раскрашивается в четыре цвета, Часть I: Разрядка». Иллинойский математический журнал . 21 : 429–490.
3. Сеймур, Пол (1977). «Матроиды со свойством max-flow min-cut». Журнал комбинаторной теории . 23 (2–3): 189–222. дои : 10.1016/0095-8956(77)90031-4 .
4. Джудин, Д.Б.; Немировский, Аркадий (1976). «Информационная сложность и эффективные методы решения выпуклых экстремальных задач». Экономика и математические методы . 12 : 357–369.
5. Хачиян, Леонид (1979). «Полиномиальный алгоритм в линейном программировании». Академия наук СССР. Доклады . 244 : 1093–1096.
6. "Леонид Хачиян, профессор, ведущий ученый-компьютерщик" . Бостон Глобус . 5 мая 2005 г..
7. Гретшель, Мартин; Ловас, Ласло ; Шрийвер, Александр (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/bf02579273.
8. Егорычев, Г.П. (1981). «Решение проблемы Ван дер Вардена для перманентов». Академия наук СССР. Доклады . 258 : 1041–1044.
9. Фаликман, Д.И. (1981). «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы». Математические заметки . 29 : 931–938.
10. Бек, Йожеф (1981). «Оценка Рота несоответствия целочисленных последовательностей почти точная». Комбинаторика . 1 (4): 319–325. дои : 10.1007/bf02579452.
11. Ленстра, HW младший (1983). «Целочисленное программирование с фиксированным числом переменных». Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . дои : 10.1287/мор.8.4.538. 
12. Люкс, Юджин М. (1982). «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время». Журнал компьютерных и системных наук . 25 (1): 42–65. дои : 10.1016/0022-0000(82)90009-5 .
13. "Компьютерный руководитель U of O получил высшую награду" . Евгений Регистр-охранник . 10 августа 1985 года..
14. Тардос, Ева (1985). «Сильно полиномиальный алгоритм циркуляции минимальной стоимости». Комбинаторика . 5 (3): 247–256. дои : 10.1007/bf02579369.
15. Кармаркар, Нарендра (1984). «Новый алгоритм линейного программирования с полиномиальным временем». Комбинаторика . 4 (4): 373–395. дои : 10.1007/bf02579150.
16. Дайер, Мартин Э .; Фриз, Алан М .; Каннан, Равиндран (1991). «Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел». Журнал АКМ . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . дои : 10.1145/102782.102783. 
17. Альфред Леман, «Неравенство ширины-длины и вырожденные проективные плоскости», У. Кук и П.Д. Сеймур (ред.), Многогранная комбинаторика, серия DIMACS по дискретной математике и теоретической информатике, том 1 (Американское математическое общество, 1990). стр. 101-105.
18. Николай Е. Мнев, "Теоремы универсальности в задаче классификации конфигурационных многообразий и выпуклых многогранников", О.Я. Виро (редактор), Семинар Ролина по топологии и геометрии, Конспекты лекций по математике, 1346 г. (Springer-Verlag, Берлин, 1988), стр. 527–544.
19. Биллера, Луи (1988). «Гомологии гладких сплайнов: общие триангуляции и гипотеза Стрэнга». Труды Американского математического общества . 310 (1): 325–340. дои : 10.2307/2001125 . JSTOR  2001125.
20. Калаи, Гил (1992). «Верхние оценки диаметра и высоты графов выпуклых многогранников». Дискретная и вычислительная геометрия . 8 (4): 363–372. дои : 10.1007/bf02293053 .
21. Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993). «Гипотеза Хадвигера о графах без K_6». Комбинаторика . 13 (3): 279–361. дои : 10.1007/bf01202354.
22. Ким, Чон Хан (1995). «Число Рамсея R (3, t ) имеет порядок t ² /log  t ». Случайные структуры и алгоритмы . 7 (3): 173–207. дои : 10.1002/rsa.3240070302. МР  1369063..
23. Гоеманс, Мишель X.; Уильямсон, Дэвид П. (1995). «Улучшенные алгоритмы аппроксимации задач максимального разреза и выполнимости с использованием полуопределенного программирования». Журнал АКМ . 42 (6): 1115–1145. дои : 10.1145/227683.227684 .
24. Мишель Конфорти, Жерар Корнюжоль и М.Р. Рао , «Разложение сбалансированных матриц», Журнал комбинаторной теории , серия B, 77 (2): 292–406, 1999.
25. "Г-н Рао, новый декан ISB" . Финансовый экспресс . 2 июля 2004 г..
26. Дж. Ф. Гилен , AMH Джерардс и А. Капур, «Исключенные несовершеннолетние для GF (4)-представимых матроидов», Журнал комбинаторной теории , серия B, 79 (2): 247–2999, 2000.
27. Цитата на премию Фулкерсона 2003 г., получено 18 августа 2012 г.
28. Бертран Генен, «Характеристика слабо двудольных графов», Журнал комбинаторной теории , серия B, 83 (1): 112–168, 2001.
29. Сатору Ивата, Лиза Флейшер, Сатору Фудзисигэ, «Комбинаторный сильно полиномиальный алгоритм для минимизации субмодулярных функций», Журнал ACM , 48 (4): 761–777, 2001.
30. Александр Шрийвер , «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время», Журнал комбинаторной теории , серия B 80 (2): 346–355, 2000.
31. Маниндра Агравал , Нирадж Каял и Нитин Саксена , «ПРАЙМЫ находятся в P», Annals of Mathematics , 160 (2): 781–793, 2004.
32. Рагунатан, MS (11 июня 2009 г.). «Индия как игрок в математику». Индус . Архивировано из оригинала 14 июня 2009 года..
33. Цитата на премию Фулкерсона 2006 г., получено 19 августа 2012 г.
34. Марк Джеррам , Алистер Синклер и Эрик Вигода, «Алгоритм аппроксимации полиномиального времени для перманента матрицы с неотрицательными элементами», Журнал ACM , 51 (4): 671–697, 2004.
35. Нил Робертсон и Пол Сеймур , «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории , серия B, 92 (2): 325–357, 2004.
36. Чудновский, Мария ; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006). «Сильная теорема о совершенном графе». Анналы математики . 164 : 51–229. arXiv : math/0212070 . дои : 10.4007/анналы.2006.164.51.
37. Цитирование премии Фулкерсона 2009 г., получено 19 августа 2012 г.
38. Спилман, Дэниел А .; Тенг, Шан-Хуа (2004). «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время». Журнал АКМ . 51 : 385–463. arXiv : математика/0212413 . дои : 10.1145/990308.990310.
39. Хейлз, Томас С. (2005). «Доказательство гипотезы Кеплера». Анналы математики . 162 (3): 1063–1183. дои : 10.4007/анналы.2005.162.1065 .
40. Фергюсон, Сэмюэл П. (2006). «Сферические упаковки, V. Пятигранные призмы». Дискретная и вычислительная геометрия . 36 : 167–204. дои : 10.1007/s00454-005-1214-y .
41. Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009). «Расширяющие потоки, геометрические вложения и разделение графов». Журнал АКМ . 56 (2): 1–37. CiteSeerX 10.1.1.310.2258 . дои : 10.1145/1502793.1502794. 
42. Йоханссон, Андерс; Кан, Джефф ; Ву, Ван Х. (2008). «Факторы в случайных графах». Случайные структуры и алгоритмы . 33 : 1–28. дои : 10.1002/rsa.20224.
43. Ловас, Ласло ; Сегеди, Балаж (2006). «Пределы плотных последовательностей графов». Журнал комбинаторной теории . 96 (6): 933–957. arXiv : math/0408173 . doi :10.1016/j.jctb.2006.05.002.
44. Сантос, Франциско (2011). «Контрпример к гипотезе Хирша». Анналы математики . 176 (1): 383–412. arXiv : 1006.2814 . дои : 10.4007/анналы.2012.176.1.7. МР  2925387.
45. Цитата на премию Фулкерсона 2015 г., получено 18 июля 2015 г.
46. Ротвосс, Томас (2017). «Соответствующий многогранник имеет экспоненциальную сложность расширения». Журнал АКМ . 64 (6): А41:1–А41:19. arXiv : 1311.2369 . дои : 10.1145/3127497. МР  3713797.
47. «Общество математической оптимизации».

Внешние ссылки

• Официальная веб-страница (МОС)
• Официальный сайт с подробной информацией о награде (сайт AMS)
• Архив прошлых лауреатов премии AMS