Premiul Fulkerson

Premiul Fulkerson  este un premiu științific pentru lucrări remarcabile în domeniul matematicii discrete , prezentat împreună de Mathematical Optimization Society (MOS) și Societatea Americană de Matematică (AMS) la Simpozionul Internațional MOS, care are loc la fiecare trei ani. . La fiecare astfel de eveniment sunt anunțate mai mult de trei nominalizări, fiecare dintre acestea putând include mai mulți oameni de știință. Premiul, 1500 de dolari , a fost plătit inițial dintr-un fond creat de prietenii lui Delbert Ray Fulkerson după moartea acestuia pentru a sprijini lucrările matematice în domeniul său.

Câștigători de premii

An Laureații Pentru ce a fost premiul?
1979 Richard Karp pentru clasificarea multor probleme importante NP-complete [1]
Kenneth Appel
Wolfgang Haken 		pentru rezolvarea problemei cu patru culori [2]
Paul Seymour pentru generalizarea teoremei Ford-Fulkerson la matroizi [3]
1982 David Yudin
Arkady Nemirovsky
Leonid Khachiyan 		pentru metoda elipsoizilor în programarea liniară [4] [5]
Georgy Egorychev
Dmitry Falikman 		pentru a demonstra conjectura lui van der Waerden despre permanenta unei matrice dublu stocastice [6]
Martin Grötschel
Laszlo Lovas
Alexander Schreiver 		pentru metoda elipsoidului în optimizarea combinatorie [7]
1985 Josef Beck pentru estimarea limitelor divergenței secvențelor întregi [8]
Hendrik Lenstra pentru o metodă eficientă de rezolvare a programelor întregi folosind geometria numerelor [9]
Eugene Luks pentru un algoritm polinom pentru determinarea graficelor izomorfe de grad mărginit [10]
1988 Eva Tardosh pentru rezolvarea problemei fluxului de cost minim printr-un algoritm de complexitate puternic polinomială [11]
Narendra Karmarkar pentru algoritmul Karmarkar [12]
1991 Martin Dyer
Alan Freese
Ravindran Kannan 		pentru un algoritm de rătăcire pentru estimarea volumului corpurilor convexe [13]
Alfred Lehman pentru analogii matricilor binare în teoria grafurilor perfecte [14]
Nikolai Mnev pentru teorema de universalitate că orice mulțime semi-algebrică este echivalentă cu spațiul realizărilor unei matroide orientate [15]
1994 Luis Billera pentru găsirea bazelor pentru spațiul funcțiilor parțial polinomiale [16]
Gil Kalai pentru lucrul la conjectura Hirsch [17]
Neil Robertson pentru soluția în șase culori a conjecturei Hadwiger [18]
1997 Jung Han Kim pentru analiza asimptotică a numerelor Ramsey R (3, t ) [19]
2000 Michel Humans
David Williamson 		pentru algoritmi de aproximare în programare semidefinită [20]
Michel Conforti
Gerard Cornuejols
Mendou Rao 		pentru algoritmul de recunoaștere a matricilor binare echilibrate în timp polinomial [21]
2003 James Galen
Bert Gerards
Ajay Kapoor 		pentru soluția GF (4) a conjecturei Rota pentru minorii matroizi [22]
Bertrand Gjunin pentru caracterizarea minorilor interziși ai grafurilor slab bipartite [23]
Satoru Iwata
Lisa Fleischer
Satoru Fujishige
Lex Shreiver 		pentru demonstrarea polinomialității puternice a minimizării submodulare [24] [25]
2006 Agrawal
Kayal
Saxena 		pentru testul Agrawala - Kayala - Saxonia [26]
Mark Errum
Alistair Sinclair
Eric Vigoda 		pentru aproximarea permanentului [27]
Neil Robertson
Paul Seymour 		pentru teorema Robertson-Seymour [28]
2009 Maria Chudnovskaya
Neil Robertson
Paul Seymour
Robin Thomas 		pentru teorema grafului puternic ideal [29]
Daniel
Spielman Teng Shanhua 		pentru analiza netezită a algoritmilor de programare liniară [30] [31]
Thomas Hales
Samuel Ferguson 		pentru a demonstra conjectura Kepler pentru cea mai densă împachetare de bile [32] [33]
2012 Sanjeev Arora
Satish Rao
Umesh Vazirani 		pentru reducerea complexității algoritmului de aproximare a separatorilor de graf [34]
Anders Johansson
Jeff Kahn
Wu Ha Wang 		pentru determinarea limitei densității arcului cu care un grafic aleator poate fi acoperit de copii disjunse ale unui grafic mai mic dat [35]
Laszlo Lovas
Balazs Szegedi 		pentru estimarea multiplicității subgrafelor în secvențe de grafice dense [36]
2015 Francisco Santos pentru un contraexemplu la conjectura Hirsch [37]
2018 Peter Allen
Julia Boettcher
Griffiths
Kohayakawa Robert Morris
 pentru Pragurile  cromatice ale graficelor
Thomas Rothvoss pentru Politopul  de potrivire are complexitate de extensie exponențială
2021 Bela Chaba
Daniela Kuhn
Allan Lo
Derek Oustus
Andrew Treglow 		pentru a demonstra conjectura 1-factorizare și conjectura de expansiune hamiltoniană [38]
Cai Jin
Xi Chen 		pentru determinarea complexității calculării funcțiilor de partiție [39]
Ken-Ichi Kawarabayashi
Mikkel Torup 		pentru dezvoltarea unui algoritm determinist pentru determinarea conectivității la margine [40]

Note

  1. ↑ Richard M. Karp, „On the computational complexity of combinatorial problems”, Networks 5: 45-68, 1975.
  2. ^ Kenneth Appel și Wolfgang Haken, „Every planar map is four colorable, Part I: Discharging”, Illinois Journal of Mathematics 21: 429-490, 1977.
  3. ↑ Paul Seymour, „Matroizii cu proprietatea min-cut de flux maxim”, Journal of Combinatorial Theory, Seria B, 23: 189-222, 1977.
  4. ↑ Nemirovskiy A.S., Yudin D.B. Complexitatea sarcinilor și eficiența metodelor de optimizare, Moscova: Nauka. Ediția principală de literatură fizică și matematică, 1979. - 384 p.
  5. ↑ L. G. Khachiyan, „ Algoritmi polinomi în programarea liniară ”, Zh. Vychisl. matematica. și mat. Phys., 20:1 (1980), 51-68.
  6. ↑ D. I. Falikman, „ Proof of Van der Waerden's conjecture on the permanent of a double stochastic matrix ”, Matem. note, 29:6 (1981), 931-938.
  7. ↑ Martin Grötschel, László Lovász și 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. ^ HW Lenstra , Jr., „Programarea întregului cu un număr fix de variabile”, 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 și Ravindran Kannan, „A random polynomial time algorithm for aproximating 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 și PD Seymour (eds.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volumul 1, (American Mathematical Society, 1990) pp. 101-105.
  15. ↑ N. E. Mnev, " Topology of multiples of combinatorial types of projective configurations and convex polyhedras. Arhiv copy of 11 martie 2014 at the Wayback Machine ", Teza candidatului , 116 pagini, Leningrad, 1986.
  16. ↑ Louis Billera, „Omology 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 și Robin Thomas, „Conjectura lui Hadwiger pentru graficele libere K 6 ”, Combinatorica 13: 279-361, 1993.
  19. ↑ Jeong Han Kim, „The Ramsey Number R(3,t) Has Order of Magnitude t 2 /log t”, Random Structures and Algorithms 7 (3): 173-207, 1995.
  20. ^ Michel X. Goemans și David P. Williamson, „Algoritmi de aproximare îmbunătățiți pentru probelsmul maxim de tăiere și satisfacție folosind programarea semidefinită”, Journal of the Association for Computing Machinery 42 (6): 1115-1145, 1995.
  21. ↑ Michele Conforti, Gérard Cornuéjols, MR Rao, „Decomposition of balanced matrices”, Journal of Combinatorial Theory, Seria B, 77 (2): 292-406, 1999.
  22. ^ JF Geelen , AMH Gerards și A. Kapoor, „The Excluded Minors for GF(4)-Representable Matroids”, Journal of Combinatorial Theory , Seria B, 79 (2): 247-2999, 2000.
  23. ↑ Bertrand Guenin, „A characterization of weakly bipartite graphs”, Journal of Combinatorial Theory , Seria B, 83 (1): 112-168, 2001.
  24. ↑ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, „A combinatorial strongly polynomial algorithm for minimiizing submodular functions”, Journal of the ACM , 48 (4): 761-777, 2001.
  25. ↑ Alexander Schrijver, „A combinatorial algorithm minimiizing submodular functions in strongly polynomial time”, Journal of Combinatorial Theory , Seria B 80 (2): 346-355, 2000.
  26. ↑ Manindra Agrawal, Neeraj Kayal și 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 și Paul Seymour, „Graph Minors. XX. Conjectura lui Wagner”, Journal of Combinatorial Theory, Seria B, 92 (2): 325-357, 2004.
  29. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour și Robin Thomas, „The strong perfect graph theorem”, Annals of Mathematics, 164: 51-229, 2006.
  30. ↑ Daniel A. Spielman și Shang-Hua Teng, „Smoothed analysis of algorithms: Why the simplex algorithm often takes polynomial time”, Journal of the ACM 51: 385-463, 2004.
  31. ↑ Mathematical Optimization Society 2009 Fulkerson Prize Citation . Preluat la 1 iulie 2019. Arhivat din original la 4 decembrie 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 și Umesh Vazirani , „Expander flows, geometric embeddings and graph partitioning”, Journal of the ACM 56: 1-37, 2009.
  35. ↑ Anders Johansson, Jeff Kahn și 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 , Seria B, 96: 933-957, 2006.
  37. ↑ Francisco Santos. Un contraexemplu la Conjectura Hirsch // Analele matematicii. - 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 descomposition conjectures”, Memoriile Societății Americane de Matematică, vol. 244, nr. 1154, 2016
  39. ↑ „Complexity of Counting CSP with Complex Weights”, Journal of the ACM, vol. 64, nr. 3, 2017
  40. ↑ „Conectivitate marginală deterministă în timp aproape liniar”, Journal of the ACM, vol. 66, nr. 1, 2018

Link -uri