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