Премия Фулкерсона
| Премия Фулкерсона | |
|---|---|
| Награжден за | Выдающиеся работы в области дискретной математики |
| Страна | Соединенные Штаты |
| Представлено | |
| Награда(ы) | $1,500 |
| Первая награда | 1979 |
| Веб-сайт | http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize  |
Премия Фулкерсона за выдающиеся работы в области дискретной математики спонсируется совместно Обществом математической оптимизации (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]
- Андерсу Йоханссону, Джеффу Кану и Ван Х. Ву за определение порога плотности ребер, выше которого случайный граф может быть покрыт непересекающимися копиями заданного меньшего графа. [42]
- Ласло Ловашу и Балашу Сегеди за характеристику кратности подграфов в последовательностях плотных графов . [43]
- 2015:
- Франсиско Сантосу Леалю за контрпример к гипотезе Хирша . [44] [45]
- 2018:
- Роберт Моррис , Ёсихару Кохаякава , Саймон Гриффитс, Питер Аллен и Джулия Бетчер за «Хроматические пороги графов».
- Томас Ротвосс за работу по расширению сложности многогранника соответствующего . [46]
- 2021:
- Бела Чаба , Даниэла Кюн , Аллан Ло , Дерик Остус и Эндрю Треглоун за доказательство гипотез 1-факторизации и разложения Гамильтона.
- Цзинь-И Цай и Си Чен о сложности подсчета CSP с комплексными весами
- Кен-Ичи Каварабаяши и Миккель Торуп за детерминированную граничную связность в почти линейном времени
Источник: официальный сайт Общества математической оптимизации. [47]
См. также [ править ]
Ссылки [ править ]
- ^ Карп, Ричард М. (1975). «О вычислительной сложности комбинаторных задач». Сети . 5 : 45–68. дои : 10.1002/net.1975.5.1.45 .
- ^ Аппель, Кеннет ; Хакен, Вольфганг (1977). «Каждая планарная карта раскрашивается в четыре цвета, Часть I: Разрядка». Иллинойсский математический журнал . 21 : 429–490.
- ^ Сеймур, Пол (1977). «Матроиды со свойством max-flow min-cut» . Журнал комбинаторной теории . 23 (2–3): 189–222. дои : 10.1016/0095-8956(77)90031-4 .
- ^ Джудин, Д.Б.; Немировский, Аркадий (1976). «Информационная сложность и эффективные методы решения выпуклых экстремальных задач». Экономика и математические методы . 12 : 357–369.
- ^ Khachiyan, Leonid (1979). "A polynomial algorithm in linear programming". Akademiia Nauk SSSR. Doklady . 244 : 1093–1096.
- ^ «Леонид Хачиян, профессор, ведущий ученый-компьютерщик» . Бостон Глобус . 5 мая 2005 года . .
- ^ Гретшель, Мартин; Ловас, Ласло ; Шрийвер, Александр (1981). «Метод эллипсоида и его последствия в комбинаторной оптимизации». Комбинаторика . 1 (2): 169–197. дои : 10.1007/bf02579273 .
- ^ Egorychev, G. P. (1981). "The solution of van der Waerden's problem for permanents". Akademiia Nauk SSSR. Doklady . 258 : 1041–1044.
- ^ Фаликман, Д.И. (1981). «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы». Математические заметки . 29 : 931–938.
- ^ Бек, Йожеф (1981). «Оценка Рота несоответствия целочисленных последовательностей почти точная». Комбинаторика . 1 (4): 319–325. дои : 10.1007/bf02579452 .
- ^ Ленстра, Х.В. младший (1983). «Целочисленное программирование с фиксированным числом переменных». Математика исследования операций . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . дои : 10.1287/moor.8.4.538 .
- ^ Люкс, Евгений М. (1982). «Изоморфизм графов ограниченной валентности можно проверить за полиномиальное время» . Журнал компьютерных и системных наук . 25 (1): 42–65. дои : 10.1016/0022-0000(82)90009-5 .
- ^ «Компьютерный руководитель Университета О получил высшую награду» . Евгений Регистр-охранник . 10 августа 1985 года .
- ^ Тардос, Ева (1985). «Сильно полиномиальный алгоритм циркуляции минимальной стоимости». Комбинаторика . 5 (3): 247–256. дои : 10.1007/bf02579369 .
- ^ Кармаркар, Нарендра (1984). «Новый алгоритм линейного программирования с полиномиальным временем». Комбинаторика . 4 (4): 373–395. дои : 10.1007/bf02579150 .
- ^ Дайер, Мартин Э .; Фриз, Алан М .; Каннан, Равиндран (1991). «Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел». Журнал АКМ . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . дои : 10.1145/102782.102783 .
- ^ Альфред Леман, «Неравенство ширины-длины и вырожденные проективные плоскости», У. Кук и П.Д. Сеймур (ред.), Многогранная комбинаторика, серия DIMACS по дискретной математике и теоретической информатике, том 1 (Американское математическое общество, 1990). стр. 101-105.
- ^ Николай Е. Мнев, "Теоремы универсальности в задаче классификации конфигурационных многообразий и выпуклых многогранников", О.Я. Виро (редактор), Семинар Ролина по топологии и геометрии, Конспекты лекций по математике, 1346 г. (Springer-Verlag, Берлин, 1988), стр. 527–544.
- ^ Биллера, Луи (1988). «Гомологии гладких сплайнов: общие триангуляции и гипотеза Стрэнга» . Труды Американского математического общества . 310 (1): 325–340. дои : 10.2307/2001125 . JSTOR 2001125 .
- ^ Калаи, Гил (1992). «Верхние оценки диаметра и высоты графов выпуклых многогранников» . Дискретная и вычислительная геометрия . 8 (4): 363–372. дои : 10.1007/bf02293053 .
- ^ Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993). «Гипотеза Хадвигера о графах без K_6». Комбинаторика . 13 (3): 279–361. дои : 10.1007/bf01202354 .
- ^ Ким, Чон Хан (1995). «Число Рамсея R (3, t ) имеет порядок величины t 2 /log t ". Случайные структуры и алгоритмы . 7 (3): 173–207. : 10.1002 /rsa.3240070302 . MR 1369063. . doi
- ^ Гоеманс, Мишель X.; Уильямсон, Дэвид П. (1995). «Улучшенные алгоритмы аппроксимации задач максимального разреза и выполнимости с использованием полуопределенного программирования» . Журнал АКМ . 42 (6): 1115–1145. дои : 10.1145/227683.227684 .
- ^ Мишель Конфорти, Жерар Корнюжоль и М.Р. Рао , «Разложение сбалансированных матриц», Журнал комбинаторной теории , серия B, 77 (2): 292–406, 1999.
- ^ «Г-н Рао, новый декан ISB» . Финансовый экспресс . 2 июля 2004 года . .
- ^ Дж. Ф. Гилен , AMH Джерардс и А. Капур, «Исключенные несовершеннолетние для GF (4)-представимых матроидов», Журнал комбинаторной теории , серия B, 79 (2): 247–2999, 2000.
- ↑ Перейти обратно: Перейти обратно: а б с Цитата о премии Фулкерсона 2003 г. , получено 18 августа 2012 г.
- ^ Бертран Генен, «Характеристика слабо двудольных графов», Журнал комбинаторной теории , серия B, 83 (1): 112–168, 2001.
- ^ Сатору Ивата, Лиза Флейшер, Сатору Фудзисигэ, «Комбинаторный сильно полиномиальный алгоритм для минимизации субмодулярных функций», Журнал ACM , 48 (4): 761–777, 2001.
- ^ Александр Шрийвер , «Комбинаторный алгоритм, минимизирующий субмодулярные функции за сильно полиномиальное время», Журнал комбинаторной теории , серия B 80 (2): 346–355, 2000.
- ^ Маниндра Агравал , Нирадж Каял и Нитин Саксена , «ПРАЙМЫ находятся в P», Annals of Mathematics , 160 (2): 781–793, 2004.
- ^ Рагунатан, М.С. (11 июня 2009 г.). «Индия как игрок в математику» . Индус . Архивировано из оригинала 14 июня 2009 года .
- ↑ Перейти обратно: Перейти обратно: а б с Цитата о премии Фулкерсона 2006 г. , получено 19 августа 2012 г.
- ^ Марк Джеррам , Алистер Синклер и Эрик Вигода , «Алгоритм аппроксимации с полиномиальным временем для перманента матрицы с неотрицательными элементами», Journal of the ACM , 51 (4): 671–697, 2004.
- ^ Нил Робертсон и Пол Сеймур , «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории , серия B, 92 (2): 325–357, 2004.
- ^ Чудновская Мария ; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006). «Сильная теорема о совершенном графе». Анналы математики . 164 : 51–229. arXiv : math/0212070 . дои : 10.4007/анналы.2006.164.51 .
- ↑ Перейти обратно: Перейти обратно: а б с Цитата на премию Фулкерсона 2009 г. , получено 19 августа 2012 г.
- ^ Спилман, Дэниел А .; Тенг, Шан-Хуа (2004). «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время». Журнал АКМ . 51 : 385–463. arXiv : математика/0212413 . дои : 10.1145/990308.990310 .
- ^ Хейлз, Томас К. (2005). «Доказательство гипотезы Кеплера» . Анналы математики . 162 (3): 1063–1183. дои : 10.4007/анналы.2005.162.1065 .
- ^ Фергюсон, Сэмюэл П. (2006). «Сферические упаковки, V. Пятигранные призмы» . Дискретная и вычислительная геометрия . 36 : 167–204. дои : 10.1007/s00454-005-1214-y .
- ^ Арора, Санджив ; Рао, Сатиш; Вазирани, Умеш (2009). «Расширяющие потоки, геометрические вложения и разделение графов». Журнал АКМ . 56 (2): 1–37. CiteSeerX 10.1.1.310.2258 . дои : 10.1145/1502793.1502794 .
- ^ Йоханссон, Андерс; Кан, Джефф ; Ву, Ван Х. (2008). «Факторы в случайных графах». Случайные структуры и алгоритмы . 33 : 1–28. дои : 10.1002/rsa.20224 .
- ^ Ловас, Ласло ; Сегеди, Балаж (2006). «Пределы плотных последовательностей графов». Журнал комбинаторной теории . 96 (6): 933–957. arXiv : math/0408173 . дои : 10.1016/j.jctb.2006.05.002 .
- ^ Сантос, Франциско (2011). «Контрпример к гипотезе Хирша». Анналы математики . 176 (1): 383–412. arXiv : 1006.2814 . дои : 10.4007/анналы.2012.176.1.7 . МР 2925387 .
- ↑ Цитата на премию Фулкерсона 2015 г. , получено 18 июля 2015 г.
- ^ Ротвосс, Томас (2017). «Соответствующий многогранник имеет экспоненциальную сложность расширения». Журнал АКМ . 64 (6): А41:1–А41:19. arXiv : 1311.2369 . дои : 10.1145/3127497 . МР 3713797 .
- ^ «Общество математической оптимизации» .