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

Премия Фулкерсона
Присуждается за	Выдающиеся документы в области дискретная математика
Страна	Соединенные Штаты
Представлено	Общество математической оптимизации Американское математическое общество
Награда (ы)	$1,500
Первый награжден	1979
Интернет сайт	http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize

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

Победители

Источник: Общество математической оптимизации

• 1979:
  • Ричард М. Карп для классификации многих важных НП-полный проблемы.^[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-мерные многогранники с п грани.^[20]
  • Нил Робертсон, Пол Сеймур и Робин Томас за шестицветный футляр Гипотеза Хадвигера.^[21]
• 1997:
  • Чон Хан Ким для поиска асимптотическая скорость роста из Числа Рамсея р(3,т).^[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:
  • Санджив Арора, Сатиш Рао и Умеш Вазирани для улучшения коэффициент аппроксимации за разделители графов и связанные с этим проблемы от ${\displaystyle O(\log n)}$ к ${\displaystyle O({\sqrt {\log n}})}$.^[41]
  • Андерс Йоханссон, Джефф Кан, и Ван Х. Ву для определения порога плотности краев, выше которого a случайный граф покрывается непересекающимися копиями данного меньшего графа.^[42]
  • Ласло Ловас и Балаж Сегеди для характеристики кратности подграфов в последовательностях плотные графы.^[43]
• 2015:
  • Франсиско Сантос Леаль за контрпример Гипотеза Хирша.^[44][45]
• 2018:
  • Роберт Моррис, Ёсихару Кохаякава, Саймон Гриффитс, Питер Аллен и Джулия Бёттчер для Хроматические пороги графов
  • Томас Ротвосс за Соответствующий многогранник имеет экспоненциальную сложность расширения

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

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

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

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

внешняя ссылка

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