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

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

Победители [ править ]

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

  • 1979:
  • 1982:
  • 1985:
    • Йожеф Бек для узких границ на расхождение в арифметической прогрессии . [10]
    • HW Lenstra, Jr. за использование геометрии чисел для решения целочисленных программ с небольшим количеством переменных во времени, полиномиальном от числа ограничений. [11]
    • Евгений М. Люкс об алгоритме изоморфизма графов с полиномиальным временем для графов максимальной ограниченной степени . [12] [13]
  • 1988:
    • Эва Тардос за нахождение обращений с минимальными затратами за сильно полиномиальное время . [14]
    • Нарендра Кармаркар за алгоритм Кармаркара для линейного программирования . [15]
  • 1991:
    • Мартин Э. Дайер , Алан М. Фриз и Равиндран Каннан за алгоритмы аппроксимации на основе случайных блужданий для объема выпуклых тел. [16]
    • Альфред Леман для 0,1-матричных аналогов теории совершенных графов . [17]
    • Николай Е. Мнев за теорему Мнева об универсальности о том , что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида . [18]
  • 1994:
    • Луи Биллера за нахождение базисов кусочно-полиномиальных функциональных пространств над триангуляциями пространства. [19]
    • Гилу Калаи за продвижение гипотезы Хирша путем доказательства субэкспоненциальных оценок диаметра d -мерных многогранников с n гранями. [20]
    • Нил Робертсон , Пол Сеймур и Робин Томас за шестицветный случай гипотезы Хадвигера . [21]
  • 1997:
    • Джеонг Хан Ким для нахождения асимптотической скорости роста в Ramsey числа R (3, т ). [22]
  • 2000:
    • Мишель X. Гоэманс и Дэвид П. Уильямсон за алгоритмы аппроксимации, основанные на полуопределенном программировании . [23]
    • Мишель Конфорти, Жерар Корнежоль и М. Р. Рао за распознавание сбалансированных матриц 0-1 за полиномиальное время . [24] [25]
  • 2003:
    • Дж. Ф. Гилен , AMH Джерардс и А. Капур для случая GF (4) гипотезы Роты о минорах матроидов . [26] [27]
    • Бертрану Генину за запрещенную минорную характеристику слабо двудольных графов (графов, многогранник двудольных подграфов которых равен 0-1). [28] [27]
    • Сатору Ивата, Лизе Флейшер, Сатору Фуджишиге и Александру Шрайверу за доказательство сильной полиномиальности субмодулярной минимизации . [29] [30] [27]
  • 2006:
    • Маниндра Агравал , Нирадж Каял и Нитин Саксена за тест примитивности AKS . [31] [32] [33]
    • Марку Джерраму , Алистеру Синклеру и Эрику Вигоду за аппроксимацию перманента . [34] [33]
    • Нил Робертсон и Пол Сеймур за теорему Робертсона – Сеймура, показывающую, что миноры графов образуют хороший квазипорядок . [35] [33]
  • 2009:
    • Марии Чудновски , Нила Робертсона, Пола Сеймура и Робина Томаса за сильную теорему о совершенном графе . [36] [37]
    • Daniel A. Шпильман и Shang-Хуа Тэн для сглаженной анализа из линейного программирования алгоритмов. [38] [37]
    • Томасу К. Хейлзу и Сэмюэлю П. Фергюсону за доказательство гипотезы Кеплера о максимально плотной упаковке сфер . [39] [40] [37]
  • 2012:
    • Сандживу Ароре , Сатишу Рао и Умешу Вазирани за улучшение отношения аппроксимации для разделителей графов и связанных задач от до . [41]
    • Андерсу Йоханссону, Джеффу Кану и Ван Х. Ву для определения порога плотности ребер, выше которого случайный граф может быть покрыт непересекающимися копиями данного меньшего графа. [42]
    • Ласло Ловасу и Балашу Сегеди за характеристику кратности подграфов в последовательностях плотных графов . [43]
  • 2015:
    • Франсиско Сантос Леалю за контрпример гипотезы Хирша . [44] [45]
  • 2018:
    • Роберт Моррис , Йошихару Кохаякава , Саймон Гриффитс, Питер Аллен и Джулия Бёттчер за хроматические пороги графов
    • Томас Ротвосс для Matching Polytope имеет сложность экспоненциального расширения

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Карп, Ричард М. (1975). «О вычислительной сложности комбинаторных задач». Сети . 5 : 45–68. DOI : 10.1002 / net.1975.5.1.45 .
  2. ^ Аппель, Кеннет ; Хакен, Вольфганг (1977). «Каждую планарную карту можно раскрасить в четыре цвета, Часть I: Разрядка». Иллинойсский журнал математики . 21 : 429–490.
  3. ^ Сеймур, Пол (1977). «Матроиды со свойством max-flow min-cut» . Журнал комбинаторной теории . 23 : 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. ^ Grötschel, Мартин; Ловас, Ласло ; Шрайвер, Александр (1981). «Метод эллипсоидов и его последствия в комбинаторной оптимизации». Combinatorica . 1 : 169–197. DOI : 10.1007 / bf02579273 .
  8. ^ Егорычев, GP (1981). «Решение проблемы Ван дер Вардена для перманентов». Академия Наук СССР. Доклады . 258 : 1041–1044.
  9. ^ Фаликман, Д. (1981). «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы». Математические заметки . 29 : 931–938.
  10. ^ Бек, Йожеф (1981). «Оценка Ротом несоответствия целочисленных последовательностей почти точна». Combinatorica . 1 (4): 319–325. DOI : 10.1007 / bf02579452 .
  11. ^ Ленстра, HW ; Младший (1983). «Целочисленное программирование с фиксированным числом переменных». Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . DOI : 10.1287 / moor.8.4.538 . 
  12. ^ Luks, Евгений М. (1982). «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время» . Журнал компьютерных и системных наук . 25 (1): 42–65. DOI : 10.1016 / 0022-0000 (82) 90009-5 .
  13. ^ "U of O Computer Chief получает высшую награду" , Юджин Регистр-гвардия , 10 августа 1985 г..
  14. ^ Tardos, Эва (1985). «Сильно полиномиальный алгоритм обращения с минимальными затратами». Combinatorica . 5 : 247–256. DOI : 10.1007 / bf02579369 .
  15. ^ Кармаркар, Нарендра (1984). «Новый алгоритм полиномиального времени для линейного программирования». Combinatorica . 4 : 373–395. DOI : 10.1007 / bf02579150 .
  16. ^ Дайер, Мартин Э .; Frieze, Алан М .; Каннан, Равиндран (1991). «Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел». Журнал ACM . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . DOI : 10.1145 / 102782.102783 . 
  17. ^ Альфред Леман, "Неравенство ширины и длины и вырожденные проективные плоскости", W. Cook и PD Seymour (ред.), Многогранная комбинаторика, серия DIMACS по дискретной математике и теоретической информатике, том 1 (Американское математическое общество, 1990) С. 101-105.
  18. ^ Николай Е. Мнев, "Теоремы универсальности по проблеме классификации многообразий конфигураций и многообразий выпуклых многогранников", О.Я. Виро (ред.), Семинар по топологии и геометрии и Рохлину, Конспект лекций по математике 1346 (Springer-Verlag, Berlin, 1988), стр. 527-544.
  19. ^ Billera Луи (1988). «Гомологии гладких сплайнов: общие триангуляции и гипотеза Стрэнга» . Труды Американского математического общества . 310 : 325–340. DOI : 10.2307 / 2001125 .
  20. Перейти ↑ Kalai, Gil (1992). «Верхние оценки диаметра и высоты графиков выпуклых многогранников» . Дискретная и вычислительная геометрия . 8 : 363–372. DOI : 10.1007 / bf02293053 .
  21. ^ Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993). «Гипотеза Хадвигера для графов без K_6». Combinatorica . 13 : 279–361. DOI : 10.1007 / bf01202354 .
  22. ^ Ким, Чон Хан (1995), «Число Рамсея R (3, t ) имеет порядок величины t 2 / log  t », Random Structures & Algorithms , 7 (3): 173–207, doi : 10.1002 / rsa. 3240070302 , Руководство по ремонту 1369063 .
  23. ^ Goemans, Мишель X .; Уильямсон, Дэвид П. (1995). «Улучшенные алгоритмы аппроксимации для максимальной вероятности сокращения и выполнимости с использованием полуопределенного программирования». Журнал ACM . 42 (6): 1115–1145. DOI : 10.1145 / 227683.227684 .
  24. ^ Мишель Конфорти, Жерар Корнежоль и М. Р. Рао , «Разложение сбалансированных матриц», Журнал комбинаторной теории , серия B, 77 (2): 292–406, 1999.
  25. ^ "MR Rao New Dean Of ISB" , Financial Express , 2 июля 2004 г..
  26. ^ Дж. Ф. Гилен , AMH Джерардс и А. Капур, «Исключенные несовершеннолетние для GF (4) -представительных матроидов», Журнал комбинаторной теории , серия B, 79 (2): 247–2999, 2000.
  27. ^ a b c Цитата из Премии Фулкерсона 2003 г. , получено 18 августа 2012 г.
  28. ^ Бертран Guenin, "Характеристика слабо двудольных графов," Журнал комбинаторной теории , серии B, 83 (1): 112-168, 2001.
  29. ^ Сатору Ивата, Лиза Флейшер, Сатору Фуджишиге, «Комбинаторный сильно полиномиальный алгоритм для минимизации субмодульных функций», Журнал ACM , 48 (4): 761–777, 2001.
  30. ^ Александр Шрайвер , "Комбинаторный алгоритм, минимизирующий субмодулярные функции за строго полиномиальное время", Журнал комбинаторной теории , серия B 80 (2): 346–355, 2000.
  31. ^ Маниндра Агравал , Neeraj Каяль и Нитин Саксена , "PRIMES в P," Анналы математики , 160 (2): 781-793, 2004.
  32. Перейти ↑ Raghunathan, MS (11 июня 2009 г.), «Индия как игрок в математике» , The Hindu.
  33. ^ a b c Цитата из Премии Фулкерсона 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 / анналы.2006.164.51 .
  37. ^ a b c Цитата из Премии Фулкерсона 2009 г. , получено 19 августа 2012 г.
  38. ^ Спилман, Дэниел А .; Тэн, Шан-Хуа (2004). «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время». Журнал ACM . 51 : 385–463. arXiv : математика / 0212413 . DOI : 10.1145 / 990308.990310 .
  39. Перейти ↑ Hales, Thomas C. (2005). «Доказательство гипотезы Кеплера» . Анналы математики . 162 : 1063–1183. DOI : 10.4007 / анналы.2005.162.1065 .
  40. ^ Фергюсон, Сэмюэл П. (2006). "Сферические упаковки, V. Пентаэдрические призмы" . Дискретная и вычислительная геометрия . 36 : 167–204. DOI : 10.1007 / s00454-005-1214-у .
  41. ^ Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009). «Расширительные потоки, геометрические вложения и разбиение графов». Журнал ACM . 56 : 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 : 933–957. arXiv : math / 0408173 . DOI : 10.1016 / j.jctb.2006.05.002 .
  44. ^ Сантос, Francisco (2011), "контрпример к гипотезе Hirsch", Annals математики , 176 (1): 383-412, Arxiv : 1006,2814 , DOI : 10,4007 / annals.2012.176.1.7 , MR 2925387 
  45. ^ Цитирование на премию Фулкерсона 2015 г. , получено 18 июля 2015 г.

Внешние ссылки [ править ]

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