Fulkerson-palkinto

Fulkerson-palkinto  on tieteellinen palkinto erinomaisesta työstä diskreetin matematiikan alalla , jonka Mathematical Optimization Society (MOS) ja American Mathematical Society (AMS) jakavat yhdessä MOS International Symposiumissa, joka järjestetään joka kolmas vuosi. . Jokaisessa tällaisessa tapahtumassa julkistetaan yli kolme ehdokasta, joista jokaisessa voi olla useita tutkijoita. Palkinto, 1500 dollaria , maksettiin alun perin Delbert Ray Fulkersonin ystävien perustamasta rahastosta hänen kuolemansa jälkeen tukemaan matemaattista työtä hänen alallaan.

Palkinnon voittajat

vuosi Palkitut Mistä palkinto myönnettiin?
1979 Richard Karp monien tärkeiden NP-täydellisten ongelmien luokitteluun [1]
Kenneth Appel
Wolfgang Haken 		neljän värin ongelman ratkaisemiseen [ 2]
Paul Seymour Ford- Fulkersonin lauseen yleistämiseksi matroideihin [3]
1982 David Yudin
Arkady Nemirovsky
Leonid Khachiyan 		ellipsoidimenetelmälle lineaarisessa ohjelmoinnissa [4] [ 5]
Georgi Egorychev
Dmitri Falikman 		todistamaan van der Waerdenin olettamus kaksinkertaisesti stokastisen matriisin pysyvästä [6]
Martin Grötschel
Laszlo Lovas
Alexander Schreiver 		ellipsoidimenetelmälle kombinatorisessa optimoinnissa [ 7 ]
1985 Josef Beck kokonaislukujonojen divergenssin rajojen arvioimiseksi [8]
Hendrik Lenstra tehokkaasta menetelmästä kokonaislukuohjelmien ratkaisemiseksi lukugeometrialla [ 9]
Eugene Luks polynomialgoritmille rajatun asteen isomorfisten graafien määrittämiseksi [10]
1988 Eva Tardosh vähimmäiskustannusvirran ongelman ratkaisemiseksi vahvasti polynomikompleksisella algoritmilla [11]
Narendra Karmarkar Karmarkar -algoritmille [12]
1991 Martin Dyer
Alan Freese
Ravindran Kannan 		vaeltavalle algoritmille kupereiden kappaleiden tilavuuden arvioimiseksi [13]
Alfred Lehman binäärimatriisien analogeille täydellisten graafien teoriassa [14]
Nikolai Mnev universaalisuuslauseen mukaan mikä tahansa puolialgebrallinen joukko vastaa orientoidun matroidin toteutusavaruutta [15]
1994 Luis Billera löytää kantaa osittain polynomifunktioiden avaruudelle [16]
Gil Kalai Hirschin arvelun parissa [17]
Neil Robertson Hadwiger -oletuksen kuusiväriselle ratkaisulle [18]
1997 Jung Han Kim Ramsey-lukujen R (3, t ) asymptoottiseen analyysiin [19]
2000 Michel Humans
David Williamson 		approksimaatioalgoritmeille puolimääräisessä ohjelmoinnissa [20]
Michel Conforti
Gerard Cornuejols
Mendou Rao 		algoritmille tasapainotettujen binäärimatriisien tunnistamiseksi polynomiajassa [21]
2003 James Galen
Bert Gerards
Ajay Kapoor 		Rota - oletuksen GF(4) -ratkaisulle matroid- alaikäisille [22]
Bertrand Gjunin heikosti kaksiosaisten graafien kiellettyjen alaikäisten luonnehtimiseen [23]
Satoru Iwata
Lisa Fleischer
Satoru Fujishige
Lex Shreiver 		submodulaarisen minimoinnin vahvan polynomiteetin osoittamiseksi [24] [25]
2006 Agrawal
Kayal
Saxena 		testiä varten Agrawala - Kayala - Saksi [26]
Mark Errum
Alistair Sinclair
Eric Vigoda 		pysyvän arvioimiseksi [ 27]
Neil Robertson
Paul Seymour 		Robertson -Seymourin lauseelle [28]
2009 Maria Chudnovskaya
Neil Robertson
Paul Seymour
Robin Thomas 		vahvasti ideaaliselle graafilauseelle [ 29]
Daniel
Spielman Teng Shanhua 		lineaaristen ohjelmointialgoritmien tasoitettuun analyysiin [30] [31]
Thomas Hales
Samuel Ferguson 		Keplerin arvelun todistamiseksi pallojen tiheimmästä pakkauksesta [32] [33]
2012 Sanjeev Arora
Satish Rao
Umesh Vazirani 		graafierottimien approksimointialgoritmin monimutkaisuuden vähentämiseksi [34]
Anders Johansson
Jeff Kahn
Wu Ha Wang 		sen kaaritiheyden rajan määrittämiseksi, jolla satunnainen graafi voidaan peittää tietyn pienemmän graafin disjunktikopioilla [35]
Laszlo Lovas
Balazs Szegedi 		aligraafien moninkertaisuuden arvioimiseen tiheiden graafien sarjoissa [36]
2015 Francisco Santos vastaesimerkkinä Hirschin olettamukselle [37]
2018 Peter Allen
Julia Boettcher
Griffiths
Kohayakawa Robert Morris
 varten Graafeiden  kromaattiset kynnykset
Thomas Rothvoss Matching Polytoope on  eksponentiaalinen laajennus monimutkaisuus
2021 Bela Chaba
Daniela Kuhn
Allan Lo
Derek Oustus
Andrew Treglow 		1-faktorisaation ja Hamiltonin laajennusoletuksen todistamiseen [38]
Cai Jin
Xi Chen 		osiofunktioiden laskennan monimutkaisuuden määrittämiseksi [39]
Ken-Ichi Kawarabayashi
Mikkel Torup 		deterministisen algoritmin kehittämiseksi reunaliitettävyyden määrittämiseksi [40]

Muistiinpanot

  1. ↑ Richard M. Karp, "Kombinatoristen ongelmien laskennallisesta monimutkaisuudesta", Networks 5: 45-68, 1975.
  2. ↑ Kenneth Appel ja Wolfgang Haken, "Jokainen tasokartta on neljä väritettävää, osa I: Purkaminen", 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. ↑ Nemirovskiy A.S., Yudin D.B. Tehtävien monimutkaisuus ja optimointimenetelmien tehokkuus, Moskova: Nauka. Fysikaalisen ja matemaattisen kirjallisuuden pääpainos, 1979. - 384 s.
  5. ↑ L. G. Khachiyan, " Polynomialgoritmit lineaarisessa ohjelmoinnissa ", Zh. Vychisl. matematiikka. ja matto. Phys., 20:1 (1980), 51-68.
  6. ↑ D. I. Falikman, " Todiste Van der Waerdenin olettamuksesta kaksinkertaisesti stokastisen matriisin pysyvästä ", Matem. muistiinpanot, 29:6 (1981), 931-938.
  7. ↑ Martin Grötschel, László Lovász ja Alexander Schrijver, "Ellipsoidimenetelmä ja sen seuraukset kombinatorisessa optimoinnissa", Combinatorica 1: 169-197, 1981.
  8. ↑ Jozsef Beck, "Rothin arvio kokonaislukujonojen poikkeavuudesta on lähes terävä", Combinatorica 1 (4): 319-325, 1981.
  9. ↑ HW Lenstra, Jr., "Kokonaislukuohjelmointi kiinteällä määrällä muuttujia", Mathematics of Operations Research 8 (4): 538-548, 1983.
  10. ↑ Eugene M. Luks, "Rajatun valenssin graafien isomorfismi voidaan testata polynomiajassa", Journal of Computer and System Sciences 25 (1): 42-65, 1982.
  11. ↑ Éva Tardos, "Voimakkaasti polynominen minimikustannuskiertoalgoritmi", Combinatorica 5: 247-256, 1985.
  12. ↑ Narendra Karmarkar, "Uusi polynomi-aikaalgoritmi lineaariseen ohjelmointiin", Combinatorica 4:373-395, 1984.
  13. ↑ Martin E. Dyer, Alan M. Frieze ja Ravindran Kannan, "Satunnainen polynomiaikaalgoritmi konveksien kappaleiden tilavuuden approksimoimiseksi", Journal of the Association for Computing Machinery 38 (1): 1-17, 1991.
  14. ↑ Alfred Lehman, "Leveys-pituus epäyhtälö ja degeneroituneet projektiivat tasot", W. Cook ja PD Seymour (toim.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, osa 1, (American Mathematical Society, 1990) s. 101-105.
  15. ↑ N. E. Mnev, " Projektiivisten konfiguraatioiden kombinatoristen tyyppien ja konveksien monitahoisten monien topologia. Arkistokopio 11. maaliskuuta 2014 Wayback Machinessa ", kandidaatin tutkielma , 116 sivua, Leningrad, 1986.
  16. ↑ Louis Billera, "Sileiden splainien homologia: Generic triangulations and a conjecture of Strang", Transactions of the AMS 310: 325-340, 1988.
  17. ↑ Gil Kalai, "Kuperan polyhedran graafien halkaisijan ja korkeuden ylärajat", Discrete and Computational Geometry 8: 363-372, 1992.
  18. ↑ Neil Robertson, Paul Seymour ja Robin Thomas, "Hadwigerin arvelu K6 -vapaille kaavioille", Combinatorica 13: 279-361, 1993.
  19. ↑ Jeong Han Kim, "Ramsey-luvun R(3,t) suuruusluokka on t 2 /log t", Random Structures and Algorithms 7 (3): 173-207, 1995.
  20. ↑ Michel X. Goemans ja David P. Williamson, "Parannetut approksimaatioalgoritmit maksimileikkaus- ja tyydyttävyysprobelsmille käyttämällä puolimääräistä ohjelmointia", 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, Series B, 77 (2): 292-406, 1999.
  22. ↑ JF Geelen, AMH Gerards ja 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 karakterisaatio heikosti bipartite graphs", Journal of Combinatorial Theory , Series B, 83 (1): 112-168, 2001.
  24. ↑ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "Kombinatorinen vahvasti polynomialgoritmi submodulaaristen funktioiden minimoimiseksi", Journal of the ACM , 48 (4): 761-777, 2001.
  25. ↑ Alexander Schrijver, "Kombinatorinen algoritmi, joka minimoi osamodulaariset funktiot vahvasti polynomisessa ajassa", Journal of Combinatorial Theory , Series B 80 (2): 346-355, 2000.
  26. ↑ Manindra Agrawal, Neeraj Kayal ja Nitin Saxena, "PRIMES on P:ssä", Annals of Mathematics, 160 (2): 781-793, 2004.
  27. ↑ Mark Jerrum, Alistair Sinclair, Eric Vigoda, "Polynomi-ajan approksimaatioalgoritmi matriisin pysyvälle ei-negatiivisilla merkinnöillä", Journal of the ACM , 51 (4): 671-697, 2004.
  28. ↑ Neil Robertson ja Paul Seymour, "Graph Minors. XX. Wagnerin olettamus", Journal of Combinatorial Theory, Series B, 92 (2): 325-357, 2004.
  29. ↑ Maria Chudnovsky, Neil Robertson, Paul Seymour ja Robin Thomas, "The strong perfect graph theorem", Annals of Mathematics, 164: 51-229, 2006.
  30. ↑ Daniel A. Spielman ja Shang-Hua Teng, "Algoritmien tasoitettu analyysi: Miksi simpleksialgoritmi kestää yleensä polynomiajan", Journal of the ACM 51: 385-463, 2004.
  31. ↑ Mathematical Optimization Society 2009 Fulkerson Prize Citation . Haettu 1. heinäkuuta 2019. Arkistoitu alkuperäisestä 4. joulukuuta 2021.
  32. ↑ Thomas C. Hales, "Todiste Keplerin olettamuksesta", 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 ja Umesh Vazirani, "Expander flows, geometric embeddings and graph partitioning", Journal of the ACM 56: 1-37, 2009.
  35. ↑ Anders Johansson, Jeff Kahn ja 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 series", Journal of Combinatorial Theory , Series B, 96: 933-957, 2006.
  37. ↑ Francisco Santos. Vastaesimerkki Hirschin arveluille // Matematiikan Annals. - 2012. - Vol. 176. - s. 383-412. - arXiv : 1006.2814 . - doi : 10.4007/annals.2012.176.1.7 . MR : 2925387 _
  38. ↑ "Todiste 1-faktorisoinnista ja Hamiltonin hajoamisoletuksista", Memoirs of the American Mathematical Society, voi. 244, nro 1154, 2016
  39. ↑ "Complexity of Counting CSP with Complex Weights", Journal of the ACM, voi. 64, nro. 3, 2017
  40. ↑ "Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, voi. 66, nro. 1, 2018

Linkit