Информационные списки

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

Перейти к навигацииПерейти к поиску

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

Лауреаты премии

Год Лауреаты За что присуждена премия
1979 Ричард Карпза классификацию многих важных NP-полных задач[1]
Кеннет Аппель[англ.]
Вольфганг Хакен		за решение задачи четырёх красок[2]
Пол Сеймурза обобщение теоремы Форда — Фалкерсона на матроиды[3]
1982 Давид Юдин
Аркадий Немировский
Леонид Хачиян		за метод эллипсоидов в линейном программировании[4][5]
Георгий Егорычев[англ.]
Дмитрий Фаликман 		за доказательство гипотезы ван дер Вардена о перманенте дважды стохастической матрицы[6]
Мартин Грётшель[нем.]
Ласло Ловас
Александр Схрейвер		за метод эллипсоидов в комбинаторной оптимизации[7]
1985 Йозеф Бек[англ.]за оценку границ расходимости целочисленных последовательностей[8]
Хендрик Ленстра за эффективный метод решения целочисленных программ с помощью геометрии чисел[9]
Юджин Лукс[англ.]за полиномиальный алгоритм определения изоморфных графов ограниченной степени[10]
1988 Эва Тардош за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложности[11]
Нарендра Кармаркарза алгоритм Кармаркара[12]
1991 Мартин Дайер[англ.]
Алан Фриз[англ.]
Равиндран Каннан		за блуждающий алгоритм оценки объёма выпуклых тел[13]
Альфред Леман за аналоги бинарных матриц в теории совершенных графов[14]
Николай Мнёв[араб. егип.]за теорему универсальности[англ.] о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида[15]
1994 Луис Бильера[англ.]за нахождение базисов пространства частично-полиномиальных функций[16]
Гиль Калай[англ.]за работу над гипотезой Хирша[17]
Нейл Робертсон[англ.]за шестицветное решение гипотезы Хадвигера[18]
1997 Чон Хан Ким[англ.]за асимптотический анализ чисел Рамсея R(3,t)[19]
2000 Мишел Хуманс[англ.]
Дэвид Уильямсон[англ.]		за алгоритмы аппроксимации в полуопределённом программировании[20]
Мишель Конфорти[нем.]
Жерар Корнюэжоль[нем.]
Менду Рао[англ.]		за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время[21]
2003 Джеймс Гейлен[англ.]
Берт Герардс
Аджай Капур 		за GF(4)-решение гипотезы Роты[англ.] для матроидных миноров[англ.][22]
Бертран Гьюнин за характеризацию запрещённых миноров слабо двудольных графов[23]
Сатору Ивата
Лиза Фляйшер
Сатору Фудзисигэ
Лекс Схрейвер		за доказательство сильной полиномиальности субмодулярной минимизации[24][25]
2006 Маниндра Агравал[англ.]
Нирадж Каял[англ.]
Нитин Саксена[англ.]		за тест Агравала — Каяла — Саксены[26]
Марк Еррум[англ.]
Алистер Синклер[англ.]
Эрик Вигода 		за аппроксимацию перманента[27]
Нейл Робертсон[англ.]
Пол Сеймур		за теорему Робертсона — Сеймура[28]
2009 Мария Чудновская[англ.]
Нейл Робертсон[англ.]
Пол Сеймур
Робин Томас		за теорему о сильно идеальных графах[29]
Дэниэл Спилмен
Тэн Шанхуа		за сглаженный анализ[англ.] алгоритмов линейного программирования[30][31]
Томас Хейлс[англ.]
Самуэль Фергюсон[нем.]		за доказательство гипотезы Кеплера для самой плотной упаковки шаров[32][33]
2012 Санджив Арора
Сатиш Рао[англ.]
Умеш Вазирани 		за снижение сложности алгоритма аппроксимации разделителей графов[34]
Андерс Йохансон
Джефф Кан[англ.]
Ву Ха Ван		за определение границы плотности дуг, с которой случайный граф может быть покрыт непересекающимися копиями данного меньшего графа[35]
Ласло Ловас
Балаш Сегеди[англ.]		за оценку кратности подграфов в последовательностях плотных графов[36]
2015 Франсиско Сантос за контрпример к гипотезе Хирша[37]
2018 Питер Аллен
Юлия Бёттхер
Саймон Гриффитс
Ёсихару Кохаякава[англ.]
Роберт Моррис[англ.]		за работу «Хроматические пороги графов» (англ. The chromatic thresholds of graphs)
Томас Ротвосс[нем.]за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» (англ. The Matching Polytope has Exponential Extension Complexity)
2021 Бела Чаба
Даниэла Кюн[англ.]
Аллан Ло
Дерек Остус[англ.]
Эндрю Треглоу 		за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях[38]
Цай Цзинь[англ.]
Си Чэнь 		за определение сложности вычисления статистических сумм[39]
Кен-Ити Каварабаяси[англ.]
Миккель Торуп[англ.]		за разработку детерминированного алгоритма определения рёберной связности[40]
2024 Бен Кузен[англ.]
Сантош Вемпала[англ.]		за технику гауссова охлаждения и -алгоритмы вычисления объёма и гауссова объёма
Цзылинь Цзян
Джонатан Тайдор
Юань Яо
Шэнтун Чжан
Юйфэй Чжао 		за работу по равноугольным прямым под заданным уголом
Натан Келлер
Ноам Лифшиц 		за метод хунты для гипеграфов и решение симплектической гипотезы Эрдёша — Хватала[41]

Примечания

  1. ↑ Richard M. Karp, «On the computational complexity of combinatorial problems», Networks 5: 45-68, 1975.
  2. ↑ Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging, " Illinois Journal of Mathematics 21: 429—490, 1977.
  3. ↑ Paul Seymour, «The matroids with the max-flow min-cut property», Journal of Combinatorial Theory, Series B, 23: 189—222, 1977.
  4. ↑ Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 с.
  5. ↑ Л. Г. Хачиян, «Полиномиальные алгоритмы в линейном программировании», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.
  6. ↑ Д. И. Фаликман, «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы», Матем. заметки, 29:6 (1981), 931—938.
  7. ↑ Martin Grötschel, László Lovász and Alexander Schrijver, «The ellipsoid method and its consequences in combinatorial optimization», Combinatorica 1: 169—197, 1981.
  8. ↑ Jozsef Beck, «Roth’s estimate of the discrepancy of integer sequences is nearly sharp», Combinatorica 1 (4): 319—325, 1981.
  9. ↑ H. W. Lenstra, Jr., "Integer programming with a fixed number of variables, " Mathematics of Operations Research 8 (4): 538—548, 1983.
  10. ↑ Eugene M. Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time, " Journal of Computer and System Sciences 25 (1): 42-65, 1982.
  11. ↑ Éva Tardos, "A strongly polynomial minimum cost circulation algorithm, " Combinatorica 5: 247—256, 1985.
  12. ↑ Narendra Karmarkar, "A new polynomial-time algorithm for linear programming, " Combinatorica 4:373-395, 1984.
  13. ↑ Martin E. Dyer, Alan M. Frieze and Ravindran Kannan, «A random polynomial time algorithm for approximating the volume of convex bodies», Journal of the Association for Computing Machinery 38 (1): 1-17, 1991.
  14. ↑ Alfred Lehman, "The width-length inequality and degenerate projective planes, " W. Cook and P. D. Seymour (eds.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 1, (American Mathematical Society, 1990) pp. 101—105.
  15. ↑ Н. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников Архивная копия от 11 марта 2014 на Wayback Machine», кандидатская диссертация, 116 стр., Ленинград, 1986.
  16. ↑ Louis Billera, «Homology of smooth splines: Generic triangulations and a conjecture of Strang», Transactions of the AMS 310: 325—340, 1988.
  17. ↑ Gil Kalai, «Upper bounds for the diameter and height of graphs of the convex polyhedra», Discrete and Computational Geometry 8: 363—372, 1992.
  18. ↑ Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger’s conjecture for K6-free graphs, " Combinatorica 13: 279—361, 1993.
  19. ↑ Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t2/log t, " Random Structures and Algorithms 7 (3): 173—207, 1995.
  20. ↑ Michel X. Goemans and David P. Williamson, «Improved approximation algorithms for the maximum cut and satisfiability probelsm using semi-definite programming», Journal of the Association for Computing Machinery 42 (6): 1115—1145, 1995.
  21. ↑ Michele Conforti, Gérard Cornuéjols, M. R. Rao, «Decomposition of balanced matrices», Journal of Combinatorial Theory, Series B, 77 (2): 292—406, 1999.
  22. ↑ J. F. Geelen, A. M. H. Gerards and A. Kapoor, «The Excluded Minors for GF(4)-Representable Matroids», Journal of Combinatorial Theory, Series B, 79 (2): 247—2999, 2000.
  23. ↑ Bertrand Guenin, «A characterization of weakly bipartite graphs», Journal of Combinatorial Theory, Series B, 83 (1): 112—168, 2001.
  24. ↑ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, «A combinatorial strongly polynomial algorithm for minimizing submodular functions», Journal of the ACM, 48 (4): 761—777, 2001.
  25. ↑ Alexander Schrijver, «A combinatorial algorithm minimizing submodular functions in strongly polynomial time», Journal of Combinatorial Theory, Series B 80 (2): 346—355, 2000.
  26. ↑ Manindra Agrawal, Neeraj Kayal and Nitin Saxena, «PRIMES is in P», Annals of Mathematics, 160 (2): 781—793, 2004.
  27. ↑ Mark Jerrum, Alistair Sinclair, Eric Vigoda, «A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries», Journal of the ACM, 51 (4): 671—697, 2004.
  28. ↑ Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner’s conjecture, " Journal of Combinatorial Theory, Series B, 92 (2): 325—357, 2004.
  29. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, «The strong perfect graph theorem», Annals of Mathematics, 164: 51-229, 2006.
  30. ↑ Daniel A. Spielman and Shang-Hua Teng, «Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time», Journal of the ACM 51: 385—463, 2004.
  31. ↑ Mathematical Optimization Society 2009 Fulkerson Prize Citation. Дата обращения: 1 июля 2019. Архивировано 4 декабря 2021 года.
  32. ↑ Thomas C. Hales, «A proof of the Kepler conjecture», Annals of Mathematics 162: 1063—1183, 2005.
  33. ↑ Samuel P. Ferguson, «Sphere Packings, V. Pentahedral Prisms», Discrete and Computational Geometry 36: 167—204, 2006.
  34. ↑ Sanjeev Arora, Satish Rao, and Umesh Vazirani, «Expander flows, geometric embeddings and graph partitioning», Journal of the ACM 56: 1-37, 2009.
  35. ↑ Anders Johansson, Jeff Kahn, and Van H. Vu, «Factors in random graphs», Random Structures and Algorithms 33: 1-28, 2008.
  36. ↑ László Lovász, Balázs Szegedy, «Limits of dense graph sequences», Journal of Combinatorial Theory, Series B, 96: 933—957, 2006.
  37. ↑ Francisco Santos. A counterexample to the Hirsch Conjecture // Annals of Mathematics. — 2012. — Vol. 176. — P. 383—412. — arXiv:1006.2814. — doi:10.4007/annals.2012.176.1.7. MR: 2925387.
  38. ↑ «Proof of the 1-factorization and Hamilton decomposition conjectures», Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016
  39. ↑ «Complexity of Counting CSP with Complex Weights», Journal of the ACM, vol. 64, no. 3, 2017
  40. ↑ «Deterministic Edge Connectivity in Near-Linear Time», Journal of the ACM, vol. 66, no. 1, 2018
  41. ↑ 2024 Delbert Ray Fulkerson Prize Awarded. News from the AMS. American Mathematical Society (23 июля 2024). Дата обращения: 25 июля 2024.

Ссылки