Википедия

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

17 Июл, 2025 / 16:05

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

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

Год Лауреаты За что присуждена премия
1979 Ричард Карп за классификацию многих важных NP-полных задач
[англ.]
Вольфганг Хакен 		за решение задачи четырёх красок
Пол Сеймур за обобщение теоремы Форда — Фалкерсона на матроиды
1982 Давид Юдин
Аркадий Немировский
Леонид Хачиян 		за метод эллипсоидов в линейном программировании
[англ.]
 за доказательство гипотезы ван дер Вардена о перманенте дважды стохастической матрицы
[нем.]
Ласло Ловас
Александр Схрейвер 		за метод эллипсоидов в комбинаторной оптимизации
1985 [англ.] за оценку границ расходимости целочисленных последовательностей
Хендрик Ленстра за эффективный метод решения целочисленных программ с помощью геометрии чисел
[англ.] за полиномиальный алгоритм определения изоморфных графов ограниченной степени
1988 Эва Тардош за решение задачи о потоке минимальной стоимости алгоритмом сильно полиномиальной сложности
Нарендра Кармаркар за алгоритм Кармаркара
1991 [англ.]
[англ.]
Равиндран Каннан 		за блуждающий алгоритм оценки объёма выпуклых тел
за аналоги бинарных матриц в теории совершенных графов
[араб. егип.] за [англ.] о том, что любое полуалгебраическое множество эквивалентно пространству реализаций ориентированного матроида
1994 [англ.] за нахождение базисов пространства частично-полиномиальных функций
[англ.] за работу над гипотезой Хирша
[англ.] за шестицветное решение гипотезы Хадвигера
1997 [англ.] за асимптотический анализ чисел Рамсея R(3,t)
2000 [англ.]
[англ.]		 за алгоритмы аппроксимации в полуопределённом программировании
[нем.]
[нем.]
[англ.]		 за алгоритм распознавания сбалансированных бинарных матриц за полиномиальное время
2003 [англ.]

 за GF(4)-решение [англ.] для [англ.]
за слабо двудольных графов



Лекс Схрейвер 		за доказательство сильной полиномиальности
2006 [англ.]
[англ.]
[англ.]		 за тест Агравала — Каяла — Саксены
[англ.]
[англ.]
 за аппроксимацию перманента
[англ.]
Пол Сеймур 		за теорему Робертсона — Сеймура
2009 [англ.]
[англ.]
Пол Сеймур
Робин Томас 		за теорему о сильно идеальных графах
Дэниэл Спилмен
Тэн Шанхуа 		за [англ.] алгоритмов линейного программирования
[англ.]
[нем.]		 за доказательство гипотезы Кеплера для самой плотной упаковки шаров
2012 Санджив Арора
[англ.]
Умеш Вазирани 		за снижение сложности алгоритма аппроксимации разделителей графов

[англ.]
Ву Ха Ван 		за определение границы плотности дуг, с которой случайный граф может быть покрыт непересекающимися копиями данного меньшего графа
Ласло Ловас
[англ.]		 за оценку кратности подграфов в последовательностях плотных графов
2015 Франсиско Сантос за контрпример к гипотезе Хирша
2018


[англ.]
[англ.]		 за работу «Хроматические пороги графов» (англ. The chromatic thresholds of graphs)
[нем.] за работу «Совпадающий политоп имеет экспоненциальную сложность расширенной формулировки» (англ. The Matching Polytope has Exponential Extension Complexity)
2021
[англ.]

[англ.]
 за доказательство гипотезы об 1-факторизации и гипотез о гамильтоновых разложениях
[англ.]
 за определение сложности вычисления статистических сумм
[англ.]
[англ.]		 за разработку детерминированного алгоритма определения рёберной связности
2024 [англ.]
[англ.]		 за технику и image-алгоритмы вычисления объёма и




за работу по равноугольным прямым под заданным уголом

за для гипеграфов и решение симплектической гипотезы Эрдёша — Хватала

Примечания

  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.

Ссылки

  • Страница премии на сайте AMS Архивная копия от 15 марта 2010 на Wayback Machine
  • Страница премии на сайте MOS Архивная копия от 12 февраля 2019 на Wayback Machine
  • Список получавших премию на сайте AMS Архивная копия от 13 ноября 2013 на Wayback Machine

Википедия, чтение, книга, библиотека, поиск, нажмите, истории, книги, статьи, wikipedia, учить, информация, история, скачать, скачать бесплатно, mp3, видео, mp4, 3gp, jpg, jpeg, gif, png, картинка, музыка, песня, фильм, игра, игры, мобильный, телефон, Android, iOS, apple, мобильный телефон, Samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Сеть, компьютер, Информация о Премия Фалкерсона, Что такое Премия Фалкерсона? Что означает Премия Фалкерсона?

Premiya Falkersona nauchnaya nagrada za vydayushiesya raboty v oblasti diskretnoj matematiki vruchaemaya sovmestno angl MOS i Amerikanskim matematicheskim obshestvom AMS na mezhdunarodnom simpoziume MOS kotoryj prohodit raz v tri goda Na kazhdom takom meropriyatii obyavlyaetsya bolee tryoh nominacij kazhdaya iz kotoryh mozhet vklyuchat neskolkih uchyonyh Razmer premii poltory tysyachi dollarov iznachalno vyplachivalas iz fonda organizovannogo druzyami Delberta Reya Falkersona posle ego smerti dlya podderzhki matematicheskih rabot v ego oblasti Laureaty premiiGod Laureaty Za chto prisuzhdena premiya1979 Richard Karp za klassifikaciyu mnogih vazhnyh NP polnyh zadach angl Volfgang Haken za reshenie zadachi chetyryoh krasokPol Sejmur za obobshenie teoremy Forda Falkersona na matroidy1982 David Yudin Arkadij Nemirovskij Leonid Hachiyan za metod ellipsoidov v linejnom programmirovanii angl za dokazatelstvo gipotezy van der Vardena o permanente dvazhdy stohasticheskoj matricy nem Laslo Lovas Aleksandr Shrejver za metod ellipsoidov v kombinatornoj optimizacii1985 angl za ocenku granic rashodimosti celochislennyh posledovatelnostejHendrik Lenstra za effektivnyj metod resheniya celochislennyh programm s pomoshyu geometrii chisel angl za polinomialnyj algoritm opredeleniya izomorfnyh grafov ogranichennoj stepeni1988 Eva Tardosh za reshenie zadachi o potoke minimalnoj stoimosti algoritmom silno polinomialnoj slozhnostiNarendra Karmarkar za algoritm Karmarkara1991 angl angl Ravindran Kannan za bluzhdayushij algoritm ocenki obyoma vypuklyh telza analogi binarnyh matric v teorii sovershennyh grafov arab egip za angl o tom chto lyuboe polualgebraicheskoe mnozhestvo ekvivalentno prostranstvu realizacij orientirovannogo matroida1994 angl za nahozhdenie bazisov prostranstva chastichno polinomialnyh funkcij angl za rabotu nad gipotezoj Hirsha angl za shesticvetnoe reshenie gipotezy Hadvigera1997 angl za asimptoticheskij analiz chisel Ramseya R 3 t 2000 angl angl za algoritmy approksimacii v poluopredelyonnom programmirovanii nem nem angl za algoritm raspoznavaniya sbalansirovannyh binarnyh matric za polinomialnoe vremya2003 angl za GF 4 reshenie angl dlya angl za slabo dvudolnyh grafovLeks Shrejver za dokazatelstvo silnoj polinomialnosti2006 angl angl angl za test Agravala Kayala Sakseny angl angl za approksimaciyu permanenta angl Pol Sejmur za teoremu Robertsona Sejmura2009 angl angl Pol Sejmur Robin Tomas za teoremu o silno idealnyh grafahDeniel Spilmen Ten Shanhua za angl algoritmov linejnogo programmirovaniya angl nem za dokazatelstvo gipotezy Keplera dlya samoj plotnoj upakovki sharov2012 Sandzhiv Arora angl Umesh Vazirani za snizhenie slozhnosti algoritma approksimacii razdelitelej grafov angl Vu Ha Van za opredelenie granicy plotnosti dug s kotoroj sluchajnyj graf mozhet byt pokryt neperesekayushimisya kopiyami dannogo menshego grafaLaslo Lovas angl za ocenku kratnosti podgrafov v posledovatelnostyah plotnyh grafov2015 Fransisko Santos za kontrprimer k gipoteze Hirsha2018 angl angl za rabotu Hromaticheskie porogi grafov angl The chromatic thresholds of graphs nem za rabotu Sovpadayushij politop imeet eksponencialnuyu slozhnost rasshirennoj formulirovki angl The Matching Polytope has Exponential Extension Complexity 2021 angl angl za dokazatelstvo gipotezy ob 1 faktorizacii i gipotez o gamiltonovyh razlozheniyah angl za opredelenie slozhnosti vychisleniya statisticheskih summ angl angl za razrabotku determinirovannogo algoritma opredeleniya ryobernoj svyaznosti2024 angl angl za tehniku i O n3 displaystyle O n 3 algoritmy vychisleniya obyoma iza rabotu po ravnougolnym pryamym pod zadannym ugolomza dlya gipegrafov i reshenie simplekticheskoj gipotezy Erdyosha HvatalaPrimechaniyaRichard 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 Nemirovskij A S Yudin D B Slozhnost zadach i effektivnost metodov optimizacii M Nauka Glavnaya redakciya fiziko matematicheskoj literatury 1979 384 s L G Hachiyan Polinomialnye algoritmy v linejnom programmirovanii Zh vychisl matem i matem fiz 20 1 1980 51 68 D I Falikman Dokazatelstvo gipotezy Van der Vardena o permanente dvazhdy stohasticheskoj matricy Matem zametki 29 6 1981 931 938 Martin Grotschel Laszlo Lovasz 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 Eva 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 N E Mnev Topologiya mnogoobrazij kombinatornyh tipov proektivnyh konfiguracij i vypuklyh mnogogrannikov Arhivnaya kopiya ot 11 marta 2014 na Wayback Machine kandidatskaya dissertaciya 116 str Leningrad 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 Gerard Cornuejols 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 neopr Data obrasheniya 1 iyulya 2019 Arhivirovano 4 dekabrya 2021 goda 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 Laszlo Lovasz Balazs 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 neopr News from the AMS American Mathematical Society 23 iyulya 2024 Data obrasheniya 25 iyulya 2024 SsylkiStranica premii na sajte AMS Arhivnaya kopiya ot 15 marta 2010 na Wayback Machine Stranica premii na sajte MOS Arhivnaya kopiya ot 12 fevralya 2019 na Wayback Machine Spisok poluchavshih premiyu na sajte AMS Arhivnaya kopiya ot 13 noyabrya 2013 na Wayback Machine

17 Июл, 2025 / 16:05
NiNa.Az

NiNa.Az

NiNa.Az - Абсолютно бесплатная система, которая делится для вас информацией и контентом 24 часа в сутки.
Взгляните
Закрыто
© 2019 NiNa.Az - Все права защищены.
Авторские права: Dadash Mammadov