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

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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Лауреаты премии[править | править код]

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

Примечания[править | править код]

  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

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

Источник — https://ru.wikipedia.org/w/index.php?title=Премия_Фалкерсона&oldid=128256003