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

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

Лауреаты премии Год Лауреаты За что присуждена премия1979 Ричард Карп за классификацию многих важных NP-полных задач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. 1982 Давид ЮдинАркадий НемировскийЛеонид Хачиян за метод эллипсоидов в линейном программированииНемировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 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. 1985 за оценку границ расходимости целочисленных последовательностей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. 1988 Эва Тардош за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложностиÉ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. 1991 Равиндран Каннан за блуждающий алгоритм оценки объёма выпуклых тел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. за о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроидаН. Е. Мнев, «Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников », кандидатская диссертация, 116 стр., Ленинград, 1986. 1994 за нахождение базисов пространства частично-полиномиальных функций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. 1997 за асимптотический анализ чисел Рамсея R(3,t)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. 2000 за алгоритмы аппроксимации в полуопределённом программировании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. 2003 Берт ГерардсАджай Капур за GF(4)-решение для 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. 2006 за тест Агравала — Каяла — Саксены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. 2009 Пол СеймурРобин Томас за теорему о сильно идеальных графах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. за доказательство гипотезы Кеплера для самой плотной упаковки шаров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. 2012 Санджив АрораУмеш Вазирани за снижение сложности алгоритма аппроксимации разделителей графов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. 2015 Франсиско Сантос за контрпример к гипотезе Хирша . 2018 Питер АлленЮлия БёттхерСаймон Гриффитс за работу «Хроматические пороги графов» () за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» () 2021 Бела ЧабаАллан ЛоЭндрю Треглоу за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях«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 за технику гауссова охлаждения и -алгоритмы вычисления объёма и гауссова объёма Цзылинь ЦзянДжонатан ТайдорЮань ЯоШэнтун ЧжанЮйфэй Чжао за работу по равноугольным прямым под заданным уголом Натан КеллерНоам Лифшиц за метод хунты для гипеграфов и решение симплектической гипотезы Эрдёша — Хватала

Примечания

Ссылки Страница премии на сайте AMS Страница премии на сайте MOS Список получавших премию на сайте AMS

Категория:Премии в области информатики Категория:Списки лауреатов премий Категория:Награды по алфавиту Категория:Награды Американского математического общества Категория:Математические награды Категория:Премии США