Просмотр кода страницы Премия Фалкерсона

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

== Лауреаты премии ==
{|class="standard"
|-
! Год
! Лауреаты
! За что присуждена премия
|-
!rowspan="3"|1979
| [[Карп, Ричард Мэннинг|Ричард Карп]]
| за классификацию многих важных [[NP-полная задача|NP-полных задач]] <ref>Richard M. Karp, «On the computational complexity of combinatorial problems», Networks 5: 45-68, 1975.</ref>
|-
| {{нп5|Аппель, Кеннет|Кеннет Аппель||Kenneth Appel}}<br>{{нп5|Хакен, Вольфганг|Вольфганг Хакен||Wolfgang Haken}}
| за решение [[проблема четырёх красок|задачи четырёх красок]] <ref>Kenneth Appel and Wolfgang Haken, "Every planar map is four colorable, Part I: Discharging, " Illinois Journal of Mathematics 21: 429—490, 1977.</ref>
|-
| [[Сеймур, Пол (математик)|Пол Сеймур]]
| за обобщение [[Теорема Форда — Фалкерсона|теоремы Форда — Фалкерсона]] на [[матроид]]ы <ref>Paul Seymour, «The matroids with the max-flow min-cut property», Journal of Combinatorial Theory, Series B, 23: 189—222, 1977.</ref>
|-




!rowspan="3"| 1982
| [[Юдин, Давид Борисович|Давид Юдин]]<br>[[Немировский, Аркадий Семёнович|Аркадий Немировский]]<br>[[Хачиян, Леонид Генрихович|Леонид Хачиян]]
| за [[метод эллипсоидов]] в [[линейное программирование|линейном программировании]] <ref>Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации, М.: Наука. Главная редакция физико-математической литературы, 1979. — 384 с.</ref> <ref>Л. Г. Хачиян, «[http://mi.mathnet.ru/zvmmf5239 Полиномиальные алгоритмы в линейном программировании]», Ж. вычисл. матем. и матем. физ., 20:1 (1980), 51-68.</ref>
|-
| {{нп5|Егорычев, Георгий Петрович|Георгий Егорычев||Georgy Egorychev}}<br>[[Дмитрий Фаликман]]
| за доказательство [[гипотеза ван дер Вардена|гипотезы ван дер Вардена]] о [[перманент]]е [[дважды стохастическая матрица|дважды стохастической матрицы]] <ref>Д. И. Фаликман, «[http://mi.mathnet.ru/mz6253 Доказательство гипотезы Ван дер Вардена о перманенте дважды стохастической матрицы]», Матем. заметки, 29:6 (1981), 931—938.</ref>
|-
| {{нп5|Грётшель, Мартин|Мартин Грётшель|de|Martin Grötschel}}<br>[[Ловас, Ласло|Ласло Ловас]]<br>[[Схрейвер, Александр|Александр Схрейвер]]
| за [[метод эллипсоидов]] в [[комбинаторная оптимизация|комбинаторной оптимизации]] <ref>Martin Grötschel, László Lovász and Alexander Schrijver, «The ellipsoid method and its consequences in combinatorial optimization», Combinatorica 1: 169—197, 1981.</ref>
|-


!rowspan="3"| 1985
| {{нп5|Бек, Йозеф|Йозеф Бек||József Beck}}
| за оценку границ расходимости [[арифметическая прогрессия|целочисленных последовательностей]] <ref>Jozsef Beck, «Roth’s estimate of the discrepancy of integer sequences is nearly sharp», Combinatorica 1 (4): 319—325, 1981.</ref>
|-
| [[Хендрик Ленстра]]
| за эффективный метод решения целочисленных программ с помощью [[геометрия чисел|геометрии чисел]] <ref>H. W. Lenstra, Jr., "Integer programming with a fixed number of variables, " Mathematics of Operations Research 8 (4): 538—548, 1983.</ref>
|-
| {{нп5|Лукс, Юджин Майкл|Юджин Лукс||Eugene M. Luks}}
| за полиномиальный алгоритм определения изоморфных графов ограниченной [[Степень вершины (теория графов)|степени]] <ref>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.</ref>
|-




!rowspan="2"| 1988
| [[Эва Тардош]]
| за решение задачи о [[Поток минимальной стоимости|потоке минимальной стоимости]] алгоритмом сильно полиномиальной сложности <ref>Éva Tardos, "A strongly polynomial minimum cost circulation algorithm, " Combinatorica 5: 247—256, 1985.</ref>
|-
| [[Кармаркар, Нарендра|Нарендра Кармаркар]]
| за [[алгоритм Кармаркара]] <ref>Narendra Karmarkar, "A new polynomial-time algorithm for linear programming, " Combinatorica 4:373-395, 1984.</ref>
|-



!rowspan="3"| 1991
| {{нп5|Дайер, Мартин Эдвард|Мартин Дайер||Martin Dyer}}<br>{{нп5|Фриз, Алан|Алан Фриз||Alan M. Frieze}}<br>[[Каннан, Равиндран|Равиндран Каннан]]
| за [[Случайное блуждание|блуждающий]] алгоритм оценки объёма выпуклых тел <ref>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.</ref>
|-
| [[Леман, Альфред|Альфред Леман]]
| за аналоги [[бинарная матрица|бинарных матриц]] в теории [[Совершенный граф|совершенных графов]] <ref>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.</ref>
|-
| {{нп5|Мнёв, Николай Евгеньевич|Николай Мнёв|arz|نيكولاى منيڤ}}
| за {{нп5|теорема универсальности|теорему универсальности||Mnev's universality theorem}} о том, что любое [[полуалгебраическое множество]] эквивалентно пространству реализаций [[ориентированный матроид|ориентированного матроида]] <ref>Н. Е. Мнев, «[http://www.pdmi.ras.ru/~mnev/mnev_phd1.pdf Топология многообразий комбинаторных типов проективных конфигураций и выпуклых многогранников]», [[кандидатская диссертация]], 116 стр., Ленинград, 1986.</ref>
|-


!rowspan="3"| 1994
| {{iw|Бильера, Луис|Луис Бильера||Louis Billera}}
| за нахождение базисов пространства частично-полиномиальных функций <ref>Louis Billera, «Homology of smooth splines: Generic triangulations and a conjecture of Strang», ''Transactions of the AMS'' 310: 325—340, 1988.</ref>
|-
| {{нп5|Калай, Гиль|Гиль Калай||Gil Kalai}}
| за работу над [[Гипотеза Хирша|гипотезой Хирша]] <ref>Gil Kalai, «Upper bounds for the diameter and height of graphs of the convex polyhedra», ''Discrete and Computational Geometry'' 8: 363—372, 1992.</ref>
|-
| {{нп5|Робертсон, Нейл (математик)|Нейл Робертсон||Neil Robertson (mathematician)}}
| за шестицветное решение [[Гипотеза Хадвигера (теория графов)|гипотезы Хадвигера]] <ref>Neil Robertson, Paul Seymour and Robin Thomas, "Hadwiger’s conjecture for K<sub>6</sub>-free graphs, " Combinatorica 13: 279—361, 1993.</ref>
|-



!rowspan="1"| 1997
| {{нп5|Чон Хан Ким|||Jeong Han Kim}}
| за асимптотический анализ [[числа Рамсея|чисел Рамсея]] ''R''(3,''t'') <ref>Jeong Han Kim, "The Ramsey Number R(3,t) Has Order of Magnitude t<sup>2</sup>/log t, " Random Structures and Algorithms 7 (3): 173—207, 1995.</ref>

|-


!rowspan="2"| 2000
| {{iw|Хуманс, Мишел|Мишел Хуманс||Michel Goemans}}<br>{{iw|Уильямсон, Дэвид|Дэвид Уильямсон||David P. Williamson}}
| за алгоритмы аппроксимации в [[полуопределённое программирование|полуопределённом программировании]] <ref>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.</ref>
|-
| {{iw|Конфорти, Мишель|Мишель Конфорти|de|Michele Conforti}}<br>{{нп5|Корнюэжоль, Жерар|Жерар Корнюэжоль|de|Gérard Cornuéjols}}<br>{{нп5|Рао, Менду Раммохан|Менду Рао||Mendu Rammohan Rao}}
| за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время <ref>Michele Conforti, Gérard Cornuéjols, M. R. Rao, «Decomposition of balanced matrices», Journal of Combinatorial Theory, Series B, 77 (2): 292—406, 1999.</ref>
|-



!rowspan="3"| 2003
| {{нп5|Гейлен, Джеймс|Джеймс Гейлен||Jim Geelen}}<br>[[Герардс, Берт|Берт Герардс]]<br>[[Капур, Аджай|Аджай Капур]]
| за [[конечное поле|GF(4)]]-решение {{нп5|Гипотеза Роты|гипотезы Роты||Rota's conjecture}} для {{нп5|Матроидный минор|матроидных миноров||Matroid minor}} <ref>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.</ref>
|-
| [[Гьюнин, Бертран|Бертран Гьюнин]]
| за [[характеризация запрещённых графов|характеризацию запрещённых миноров]] слабо [[двудольный граф|двудольных графов]] <ref>Bertrand Guenin, «A characterization of weakly bipartite graphs», ''Journal of Combinatorial Theory'', Series B, 83 (1): 112—168, 2001.</ref>
|-
| [[Ивата, Сатору (математик)|Сатору Ивата]]<br>[[Фляйшер, Лиза|Лиза Фляйшер]]<br>[[Фудзисигэ, Сатору|Сатору Фудзисигэ]]<br>[[Схрейвер, Александр|Лекс Схрейвер]]
| за доказательство сильной полиномиальности [[субмодулярная минимизация|субмодулярной минимизации]] <ref>Satoru Iwata, Lisa Fleischer, Satoru Fujishige, «A combinatorial strongly polynomial algorithm for minimizing submodular functions», ''Journal of the ACM'', 48 (4): 761—777, 2001.</ref> <ref>Alexander Schrijver, «A combinatorial algorithm minimizing submodular functions in strongly polynomial time», ''Journal of Combinatorial Theory'', Series B 80 (2): 346—355, 2000.</ref>
|-



!rowspan="3"| 2006
| {{нп5|Агравал, Маниндра|Маниндра Агравал||Manindra Agrawal}}<br>{{нп5|Каял, Нирадж|Нирадж Каял||Neeraj Kayal}}<br>{{нп5|Саксена, Нитин|Нитин Саксена||Nitin Saxena}}
| за [[тест Агравала — Каяла — Саксены]] <ref>Manindra Agrawal, Neeraj Kayal and Nitin Saxena, «PRIMES is in P», Annals of Mathematics, 160 (2): 781—793, 2004.</ref>
|-
| {{нп5|Еррум, Марк|Марк Еррум||Mark Jerrum}}<br>{{нп5|Синклер, Алистер (математик)|Алистер Синклер||Alistair Sinclair}}<br>[[Вигода, Эрик|Эрик Вигода]]
| за [[аппроксимация|аппроксимацию]] [[перманент]]а <ref>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.</ref>
|-
| {{нп5|Робертсон, Нейл (математик)|Нейл Робертсон||Neil Robertson (mathematician)}}<br>[[Сеймур, Пол (математик)|Пол Сеймур]]
| за [[Теорема Робертсона — Сеймура|теорему Робертсона — Сеймура]] <ref>Neil Robertson and Paul Seymour, "Graph Minors. XX. Wagner’s conjecture, " Journal of Combinatorial Theory, Series B, 92 (2): 325—357, 2004.</ref>
|-


!rowspan="3"| 2009
| {{нп5|Чудновская, Мария|Мария Чудновская||Maria Chudnovsky}}<br>{{нп5|Робертсон, Нейл (математик)|Нейл Робертсон||Neil Robertson (mathematician)}}<br>[[Сеймур, Пол (математик)|Пол Сеймур]]<br>[[Томас, Робин (математик)|Робин Томас]]
| за [[Сильная гипотеза о совершенных графах|теорему о сильно идеальных графах]] <ref>Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, «The strong perfect graph theorem», Annals of Mathematics, 164: 51-229, 2006.</ref>
|-
| [[Дэниэл Спилмен]]<br>[[Тэн Шанхуа]]
| за {{нп5|сглаженный анализ|||Smoothed analysis}} алгоритмов [[линейное программирование|линейного программирования]] <ref>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.</ref><ref>[http://www.mathopt.org/?nav=fulkerson_2009 Mathematical Optimization Society 2009 Fulkerson Prize Citation]</ref>
|-
| {{нп5|Хейлс, Томас Каллистер|Томас Хейлс||Thomas Callister Hales}}<br>{{iw|Фергюсон, Самуэль|Самуэль Фергюсон|de|Samuel P. Ferguson}}
| за доказательство [[Гипотеза Кеплера|гипотезы Кеплера]] для самой плотной [[Упаковка шаров|упаковки шаров]] <ref>Thomas C. Hales, «A proof of the Kepler conjecture», Annals of Mathematics 162: 1063—1183, 2005.</ref> <ref>Samuel P. Ferguson, «Sphere Packings, V. Pentahedral Prisms», Discrete and Computational Geometry 36: 167—204, 2006.</ref>
|-



!rowspan="3"| 2012
| [[Санджив Арора]]<br>{{iw|Рао, Сатиш|Сатиш Рао||Satish Rao}}<br>[[Умеш Вазирани]]
| за снижение сложности алгоритма аппроксимации разделителей графов <ref>Sanjeev Arora, Satish Rao, and Umesh Vazirani, «Expander flows, geometric embeddings and graph partitioning», Journal of the ACM 56: 1-37, 2009.</ref>
|-
| [[Йохансон, Андерс|Андерс Йохансон]]<br>{{нп5|Кан, Джефф|Джефф Кан||Jeff Kahn}}<br>[[Ву Ха Ван]]
| за определение границы плотности дуг, с которой случайный граф может быть покрыт непересекающимися копиями данного меньшего графа <ref>Anders Johansson, Jeff Kahn, and Van H. Vu, «Factors in random graphs», Random Structures and Algorithms 33: 1-28, 2008.</ref>
|-
| [[Ласло Ловас]]<br>{{iw|Сегеди, Балаш|Балаш Сегеди||Balázs Szegedy}}
| за оценку кратности подграфов в последовательностях [[Плотный граф|плотных графов]] <ref>László Lovász, Balázs Szegedy, «Limits of dense graph sequences», ''Journal of Combinatorial Theory'', Series B, 96: 933—957, 2006.</ref>
|-

!rowspan="1"| 2015
| [[Франсиско Сантос]]
| за контрпример к [[Гипотеза Хирша|гипотезе Хирша]] <ref>{{публикация|статья|автор=Francisco Santos|заглавие=A counterexample to the Hirsch Conjecture|год=2012|издание=Annals of Mathematics|volume=176|pages=383—412|doi=10.4007/annals.2012.176.1.7|arxiv=1006.2814}} {{MR|2925387}}.</ref>
|-


!rowspan="2"| 2018
| [[Аллен, Питер|Питер Аллен]]<br>[[Бёттхер, Юлия|Юлия Бёттхер]]<br>[[Гриффитс, Саймон|Саймон Гриффитс]]<br>{{iw|Кохаякава, Ёсихару|Ёсихару Кохаякава||Yoshiharu Kohayakawa}}<br>{{iw|Моррис, Роберт (математик)|Роберт Моррис||Robert Morris (mathematician)}}
| за работу «Хроматические пороги графов» ({{lang-en|The chromatic thresholds of graphs}})
|-
| {{iw|Ротвосс, Томас|Томас Ротвосс|de|Thomas Rothvoß}}
| за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» ({{lang-en|The Matching Polytope has Exponential Extension Complexity}})
|-


!rowspan="3"| 2021
| [[Бела Чаба]]<br>{{нп5|Кюн, Даниэла|Даниэла Кюн||Daniela Kühn}}<br>[[Аллан Ло]]<br>{{нп5|Остус, Дерек|Дерек Остус||Deryk Osthus}}<br>[[Эндрю Треглоу]]
| за доказательство [[Факторизация графа|гипотезы об 1-факторизации]] и гипотез о [[Гамильтоново разложение|гамильтоновых разложениях]] <ref>"Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016</ref>
|-
| {{нп5|Цзинь, Цай|Цай Цзинь||Jin-Yi Cai}}<br>[[Си Чэнь]]
| за определение [[класс сложности|сложности]] вычисления [[Статистическая сумма|статистических сумм]] <ref>"Complexity of Counting CSP with Complex Weights", Journal of the ACM, vol. 64, no. 3, 2017</ref>
|-
| {{нп5|Каварабаяси, Кен-Ичи|Кен-Ичи Каварабаяси||Ken-ichi Kawarabayashi}}<br>{{нп5|Торуп, Миккель|Миккель Торуп||Mikkel Thorup}}
| за разработку детерминированного алгоритма определения [[Рёберно k-связный граф|реберной связности]] <ref>"Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, vol. 66, no. 1, 2018</ref>
|}

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.ams.org/prizes/fulkerson-prize.html Страница премии на сайте AMS]
* [http://www.mathopt.org/?nav=fulkerson Страница премии на сайте MOS]
* [http://www.ams.org/profession/prizes-awards/pabrowse Список получавших премию на сайте AMS]

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