Премия Фалкерсона
Материал из Википедии — свободной энциклопедии
Премия Фалкерсона — научная награда за выдающиеся работы в области дискретной математики, вручаемая совместно Обществом математической оптимизации[англ.] (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] |
Примечания
[править | править код]- ↑ Richard M. Karp, «On the computational complexity of combinatorial problems», Networks 5: 45-68, 1975.
- ↑ Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging, " Illinois Journal of Mathematics 21: 429—490, 1977.
- ↑ Paul Seymour, «The matroids with the max-flow min-cut property», Journal of Combinatorial Theory, Series B, 23: 189—222, 1977.
- ↑ Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 с.
- ↑ Л. Г. Хачиян, «Полиномиальные алгоритмы в линейном программировании», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.
- ↑ Д. И. Фаликман, «Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы», Матем. заметки, 29:6 (1981), 931—938.
- ↑ Martin Grötschel, László Lovász and Alexander Schrijver, «The ellipsoid method and its consequences in combinatorial optimization», Combinatorica 1: 169—197, 1981.
- ↑ Jozsef Beck, «Roth’s estimate of the discrepancy of integer sequences is nearly sharp», Combinatorica 1 (4): 319—325, 1981.
- ↑ H. W. Lenstra, Jr., "Integer programming with a fixed number of variables, " Mathematics of Operations Research 8 (4): 538—548, 1983.
- ↑ 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.
- ↑ Éva Tardos, "A strongly polynomial minimum cost circulation algorithm, " Combinatorica 5: 247—256, 1985.
- ↑ Narendra Karmarkar, "A new polynomial-time algorithm for linear programming, " Combinatorica 4:373-395, 1984.
- ↑ 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.
- ↑ 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.
- ↑ Н. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников Архивная копия от 11 марта 2014 на Wayback Machine», кандидатская диссертация, 116 стр., Ленинград, 1986.
- ↑ Louis Billera, «Homology of smooth splines: Generic triangulations and a conjecture of Strang», Transactions of the AMS 310: 325—340, 1988.
- ↑ Gil Kalai, «Upper bounds for the diameter and height of graphs of the convex polyhedra», Discrete and Computational Geometry 8: 363—372, 1992.
- ↑ Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger’s conjecture for K6-free graphs, " Combinatorica 13: 279—361, 1993.
- ↑ 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.
- ↑ 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.
- ↑ Michele Conforti, Gérard Cornuéjols, M. R. Rao, «Decomposition of balanced matrices», Journal of Combinatorial Theory, Series B, 77 (2): 292—406, 1999.
- ↑ 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.
- ↑ Bertrand Guenin, «A characterization of weakly bipartite graphs», Journal of Combinatorial Theory, Series B, 83 (1): 112—168, 2001.
- ↑ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, «A combinatorial strongly polynomial algorithm for minimizing submodular functions», Journal of the ACM, 48 (4): 761—777, 2001.
- ↑ Alexander Schrijver, «A combinatorial algorithm minimizing submodular functions in strongly polynomial time», Journal of Combinatorial Theory, Series B 80 (2): 346—355, 2000.
- ↑ Manindra Agrawal, Neeraj Kayal and Nitin Saxena, «PRIMES is in P», Annals of Mathematics, 160 (2): 781—793, 2004.
- ↑ 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.
- ↑ Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner’s conjecture, " Journal of Combinatorial Theory, Series B, 92 (2): 325—357, 2004.
- ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, «The strong perfect graph theorem», Annals of Mathematics, 164: 51-229, 2006.
- ↑ 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.
- ↑ Mathematical Optimization Society 2009 Fulkerson Prize Citation . Дата обращения: 1 июля 2019. Архивировано 4 декабря 2021 года.
- ↑ Thomas C. Hales, «A proof of the Kepler conjecture», Annals of Mathematics 162: 1063—1183, 2005.
- ↑ Samuel P. Ferguson, «Sphere Packings, V. Pentahedral Prisms», Discrete and Computational Geometry 36: 167—204, 2006.
- ↑ Sanjeev Arora, Satish Rao, and Umesh Vazirani, «Expander flows, geometric embeddings and graph partitioning», Journal of the ACM 56: 1-37, 2009.
- ↑ Anders Johansson, Jeff Kahn, and Van H. Vu, «Factors in random graphs», Random Structures and Algorithms 33: 1-28, 2008.
- ↑ László Lovász, Balázs Szegedy, «Limits of dense graph sequences», Journal of Combinatorial Theory, Series B, 96: 933—957, 2006.
- ↑ 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.
- ↑ «Proof of the 1-factorization and Hamilton decomposition conjectures», Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016
- ↑ «Complexity of Counting CSP with Complex Weights», Journal of the ACM, vol. 64, no. 3, 2017
- ↑ «Deterministic Edge Connectivity in Near-Linear Time», Journal of the ACM, vol. 66, no. 1, 2018
- ↑ 2024 Delbert Ray Fulkerson Prize Awarded . News from the AMS. American Mathematical Society (23 июля 2024). Дата обращения: 25 июля 2024.
Ссылки
[править | править код]- Страница премии на сайте AMS Архивная копия от 15 марта 2010 на Wayback Machine
- Страница премии на сайте MOS Архивная копия от 12 февраля 2019 на Wayback Machine
- Список получавших премию на сайте AMS Архивная копия от 13 ноября 2013 на Wayback Machine
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.