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

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

Награда

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

Победители

• 1979:
  • Ричарду М. Карпу за классификацию многих важных NP-полных задач. ^[1]
  • Кеннет Аппель и Вольфганг Хакен за теорему о четырех красках . ^[2]
  • Пол Сеймур за обобщение теоремы о максимальном потоке и минимальном разрезе на матроиды . ^[3]
• 1982:
  • Д.Б. Юдину, Аркадию Немировскому , Леониду Хачияну , Мартину Гретшелю , Ласло Ловасу и Александру Шрийверу за метод эллипсоидов в линейном программировании и комбинаторной оптимизации . ^{[4] [5] [6] [7]}
  • Г. П. Егорычеву и Д. И. Фаликману за доказательство гипотезы Ван дер Вардена о том, что матрица со всеми равными элементами имеет наименьший перманент среди всех дважды стохастических матриц . ^{[8] [9]}
• 1985:
  • Йожеф Бек за точные оценки расхождения арифметических прогрессий . [ ^10]
  • HW Lenstra Jr. за использование геометрии чисел для решения целочисленных программ с несколькими переменными за время, полиномиальное по числу ограничений. ^[11]
  • Юджин М. Люкс за полиномиальный алгоритм изоморфизма графов для графов ограниченной максимальной степени . ^{[12] [13]}
• 1988:
  • Эве Тардос за нахождение циркуляций с минимальной стоимостью за строго полиномиальное время . ^[14]
  • Нарендра Кармаркар за алгоритм Кармаркара для линейного программирования . ^[15]
• 1991:
  • Мартин Э. Дайер , Алан М. Фриз и Равиндран Каннан за алгоритмы аппроксимации на основе случайного блуждания для объема выпуклых тел. ^[16]
  • Альфред Леман для 0,1-матричных аналогов теории совершенных графов . ^[17]
  • Николай Е. Мнев за теорему универсальности Мнева о том, что каждое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида . ^[18]
• 1994:
  • Луи Биллера за нахождение базисов кусочно-полиномиальных функциональных пространств над триангуляциями пространства. ^[19]
  • Джилу Калаи за достижение прогресса в гипотезе Хирша путем доказательства субэкспоненциальных границ диаметра d -мерных многогранников с n гранями. ^[20]
  • Нил Робертсон , Пол Сеймур и Робин Томас для шестицветного случая гипотезы Хадвигера . ^[21]
• 1997:
  • Чон Хан Ким за нахождение асимптотической скорости роста чисел Рамсея R (3, t ). ^[22]
• 2000:
  • Мишель Х. Гоэманс и Дэвид П. Уильямсон за аппроксимационные алгоритмы, основанные на полуопределенном программировании . ^[23]
  • Мишель Конфорти, Жерар Корнуэжоль и М. Р. Рао за распознавание сбалансированных матриц 0-1 за полиномиальное время . ^{[24] [25]}
• 2003:
  • JF Geelen , AMH Gerards и A. Kapoor для случая 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]

• 2024:
  • Бен Казинс и Сантош Вемпала за гауссовское охлаждение и алгоритмы для объема и гауссова объема ${\displaystyle O^{*}(n^{3})}$
  • Цзылин Цзян, Джонатан Тидор, Юань Яо, Шэнтун Чжан и Юфэй Чжао за равноугольные линии с фиксированным углом
  • Натан Келлер и Ноам Лифшиц за «Метод хунты для гиперграфов и гипотезу симплекса Эрдёша–Хватала»

Источник: официальный сайт Американского математического общества. ^[48]

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

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

Ссылки

1. Карп, Ричард М. (1975). «О вычислительной сложности комбинаторных задач». Networks . 5 : 45–68. doi :10.1002/net.1975.5.1.45.
2. Аппель, Кеннет ; Хакен, Вольфганг (1977). «Каждая плоская карта может быть раскрашена четырьмя красками, Часть I: Разрядка». Illinois Journal of Mathematics . 21 : 429–490.
3. Сеймур, Пол (1977). «Матроиды со свойством максимального потока и минимального разреза». Журнал комбинаторной теории . 23 (2–3): 189–222. doi : 10.1016/0095-8956(77)90031-4 .
4. Юдин, ДБ; Немировский, Аркадий (1976). «Информационная сложность и эффективные методы решения выпуклых экстремальных задач». Экономика и математические методы . 12 : 357–369.
5. Хачиян, Леонид (1979). «Полиномиальный алгоритм в линейном программировании». Академия наук СССР. Доклады . 244 : 1093–1096.
6. "Леонид Хачиян, профессор, ведущий специалист по информатике". Boston Globe . 5 мая 2005 г..
7. Грётшель, Мартин; Ловас, Ласло ; Шрайвер, Александр (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Combinatorica . 1 (2): 169–197. doi :10.1007/bf02579273.
8. Егорычев, Г.П. (1981). «Решение проблемы Ван дер Вардена для перманентов». Академия наук СССР. Доклады . 258 : 1041–1044.
9. Фаликман, Д.И. (1981). «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы». Математические заметки . 29 : 931–938.
10. Бек, Йожеф (1981). «Оценка Рота расхождения целочисленных последовательностей почти точна». Combinatorica . 1 (4): 319–325. doi :10.1007/bf02579452.
11. Lenstra, HW Jr. (1983). «Целочисленное программирование с фиксированным числом переменных». Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. 
12. Люкс, Юджин М. (1982). «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время». Журнал компьютерных и системных наук . 25 (1): 42–65. doi : 10.1016/0022-0000(82)90009-5 .
13. "U of O Computer Chief Gets Top Award". Юджин Регистр-Гард . 10 августа 1985 г..
14. Тардос, Эва (1985). «Сильно полиномиальный алгоритм циркуляции минимальной стоимости». Combinatorica . 5 (3): 247–256. doi :10.1007/bf02579369.
15. Кармаркар, Нарендра (1984). «Новый алгоритм полиномиального времени для линейного программирования». Combinatorica . 4 (4): 373–395. doi :10.1007/bf02579150.
16. Дайер, Мартин Э .; Фриз, Алан М .; Каннан, Равиндран (1991). «Случайный полиномиальный алгоритм времени для аппроксимации объема выпуклых тел». Журнал ACM . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . doi :10.1145/102782.102783. 
17. Альфред Леман, «Неравенство ширины-длины и вырожденные проективные плоскости», У. Кук и П. Д. Сеймур (ред.), Полиэдральная комбинаторика, серия DIMACS по дискретной математике и теоретической информатике, том 1, (Американское математическое общество, 1990) стр. 101-105.
18. Николай Е. Мнев, «Теоремы универсальности в задаче классификации многообразий конфигураций и многообразий выпуклых многогранников», О. Я. Виро (ред.), Топология и геометрия-Рохлинский семинар, заметки лекций по математике 1346 (Springer-Verlag, Берлин, 1988) стр. 527-544.
19. Биллера, Луис (1988). «Гомология гладких сплайнов: общие триангуляции и гипотеза Стрэнга». Труды Американского математического общества . 310 (1): 325–340. doi : 10.2307/2001125 . JSTOR  2001125.
20. Калай, Гил (1992). «Верхние оценки диаметра и высоты графиков выпуклых многогранников». Дискретная и вычислительная геометрия . 8 (4): 363–372. doi : 10.1007/bf02293053 .
21. Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993). «Гипотеза Хадвигера для графов, свободных от K_6». Combinatorica . 13 (3): 279–361. doi :10.1007/bf01202354.
22. Ким, Чжон Хан (1995). «Число Рамсея R (3, t ) имеет порядок величины t ² /log  t ». Случайные структуры и алгоритмы . 7 (3): 173–207. doi :10.1002/rsa.3240070302. MR  1369063..
23. Goemans, Michel X.; Williamson, David P. (1995). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». Journal of the ACM . 42 (6): 1115–1145. doi : 10.1145/227683.227684 .
24. Мишель Конфорти, Жерар Корнуэжоль и М. Р. Рао , «Разложение сбалансированных матриц», Журнал комбинаторной теории , Серия B, 77 (2): 292–406, 1999.
25. "Г-н Рао — новый декан ISB". Financial Express . 2 июля 2004 г..
26. JF Geelen , AMH Gerards и A. Kapoor, «Исключенные миноры для 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. Raghunathan, MS (11 июня 2009 г.). "Индия как игрок в математике". The Hindu . Архивировано из оригинала 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 . doi :10.4007/annals.2006.164.51.
37. Ссылка на премию Фулкерсона 2009 года, получена 19 августа 2012 г.
38. Шпильман, Дэниел А .; Тенг, Шан-Хуа (2004). «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время». Журнал ACM . 51 : 385–463. arXiv : math/0212413 . doi :10.1145/990308.990310.
39. Хейлз, Томас С. (2005). «Доказательство гипотезы Кеплера». Annals of Mathematics . 162 (3): 1063–1183. doi : 10.4007/annals.2005.162.1065 .
40. Фергюсон, Сэмюэл П. (2006). «Упаковки сфер, V. Пентаэдральные призмы». Дискретная и вычислительная геометрия . 36 : 167–204. doi : 10.1007/s00454-005-1214-y .
41. Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009). «Расширяющиеся потоки, геометрические вложения и разбиение графов». Журнал ACM . 56 (2): 1–37. CiteSeerX 10.1.1.310.2258 . doi :10.1145/1502793.1502794. 
42. Йоханссон, Андерс; Кан, Джефф ; Ву, Ван Х. (2008). «Факторы в случайных графах». Случайные структуры и алгоритмы . 33 : 1–28. doi :10.1002/rsa.20224.
43. Ловас, Ласло ; Сегеди, Балаж (2006). «Пределы плотных последовательностей графов». Журнал комбинаторной теории . 96 (6): 933–957. arXiv : math/0408173 . doi :10.1016/j.jctb.2006.05.002.
44. Сантос, Франциско (2011). «Контрпример к гипотезе Хирша». Annals of Mathematics . 176 (1): 383–412. arXiv : 1006.2814 . doi : 10.4007/annals.2012.176.1.7. MR  2925387.
45. Цитата из Премии Фулкерсона 2015 года, получена 18 июля 2015 г.
46. Ротвосс, Томас (2017). «Соответствующий многогранник имеет экспоненциальную сложность расширения». Журнал ACM . 64 (6): A41:1–A41:19. arXiv : 1311.2369 . doi : 10.1145/3127497. MR  3713797.
47. "Премия Фулкерсона". Премии MOS . Общество математической оптимизации . Получено 25 июля 2024 г.
48. "Присуждена премия Делберта Рэя Фулкерсона 2024 года". Новости AMS . Американское математическое общество. 23 июля 2024 г. Получено 25 июля 2024 г.

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

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