Fulkerson -Preis
| Fulkerson -Preis | |
|---|---|
| Verliehen für | Herausragende Papiere im Bereich von Diskrete Mathematik |
| Land | Vereinigte Staaten |
| Präsentiert von | Mathematische Optimierungsgesellschaft American Mathematical Society |
| Belohnung) | $ 1.500 |
| Zuerst ausgezeichnet | 1979 |
| Webseite | http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize  |
Das Fulkerson -Preis für herausragende Papiere im Bereich von Diskrete Mathematik wird gemeinsam von der gesponsert Mathematische Optimierungsgesellschaft (Mos) und die American Mathematical Society (AMS). Auf jedem (dreijährigen) internationalen Symposium der MOS werden jeweils bis zu drei Auszeichnungen von jeweils 1.500 US -Dollar verliehen. Ursprünglich wurden die Preise aus einem von den AMS verwalteten Gedenkfonds ausgezahlt, das von Freunden des späten Unternehmens gegründet wurde Delbert Ray Fulkerson Förderung der mathematischen Exzellenz in den Forschungsgebieten, die durch seine Arbeit veranschaulicht werden. Die Preise werden jetzt durch eine von Abgeordneten verwaltete Stiftung finanziert.
Gewinner
Quelle: Mathematische Optimierungsgesellschaft
- 1979:
- Richard M. Karp um viele wichtige zu klassifizieren NP-Complete Probleme.[1]
- Kenneth Appel und Wolfgang Haken für die Vier Farbsatz.[2]
- Paul Seymour zur Verallgemeinerung der Max-Flow Min-Cut-Theorem zu Matroiden.[3]
- 1982:
- D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grötschel, László Lovász und Alexander Schrijver für die Ellipsoid -Methode in Lineares Programmieren und Kombinatorische Optimierung.[4][5][6][7]
- G. P. Egorychev und D. I. Falikman für den Beweis Van der WaerdenDie Vermutung, dass die Matrix mit allen Einträgen gleich die kleinste hat dauerhaft von jedem doppelt stochastische Matrix.[8][9]
- 1985:
- Jozsef Beck für enge Grenzen auf der Diskrepanz von Arithmetische Fortschritte.[10]
- H. W. Lenstra, Jr. für die Verwendung der Geometrie der Zahlen lösen Ganzzahlprogramme mit wenigen Variablen in der Zeit Polynom in der Anzahl der Einschränkungen.[11]
- Eugene M. Luks Für ein Polynomzeit Graph -Isomorphismus -Algorithmus Für Grafiken von begrenzt maximaler Grad.[12][13]
- 1988:
- 1991:
- Martin E. Dyer, Alan M. Frieze und Ravindran Kannan zum zielloser Spaziergang-basierend Näherungsalgorithmen Für das Volumen der konvexen Körper.[16]
- Alfred Lehman für 0,1-matrix Analoga der Theorie von Perfekte Grafiken.[17]
- Nikolai E. Mnev für MNEVs Universalitätstheorem, dass jeder semialgebraische Set dem Raum der Realisierungen eines entspricht Orientierte Matroid.[18]
- 1994:
- Louis Billera zum Auffinden von Basen von stückweise polynomialen Funktionsräumen über Triangulationen des Weltraums.[19]
- Gil Kalai für Fortschritte auf der Hirsch -Vermutung durch Nachweis von Subtonponentialgrenzen am Durchmesser von d-Dimensionale Polytope mit n Facetten.[20]
- Neil Robertson, Paul Seymour und Robin Thomas für den sechsfarbigen Fall von Hadwigers Vermutung.[21]
- 1997:
- Jeong Han Kim für das Finden der Asymptotische Wachstumsrate des Ramsey -Zahlen R(3,t).[22]
- 2000:
- Michel X. Goemans und David P. Williamson zum Näherungsalgorithmen bezogen auf Semidefinite Programmierung.[23]
- Michele corti, Gérard Cornuéjols, und M. R. Rao zum Erkennen ausgeglichene 0-1 Matrizen in Polynomzeit.[24][25]
- 2003:
- J. F. GeelenA. M. H. Gerards und A. Kapoor für die GF (4) Fall von Rotas Vermutung an Matroid -Minderjährige.[26][27]
- Bertrand Guenin für a Verbotene geringfügige Charakterisierung der schwach zweipartneren Graphen (Diagramme, deren zweipartnerer Subgraph-Polytope 0-1 beträgt).[28][27]
- Satoru Iwata, Lisa Fleischer, Satoru Fujishige und Alexander Schrijver zum Zeigen submoduläre Minimierung stark polynomisch sein.[29][30][27]
- 2006:
- Manindra Agrawal, Neeraj Kayal und Nitin Saxenafür die ASS -Primalitätstest.[31][32][33]
- Mark Jerrum, Alistair Sinclair und Eric Vigoda, für Annäherung an die Ständigen.[34][33]
- Neil Robertson und Paul Seymourfür die Robertson -Seymour -Theorem Zeigt das Graph Minderjährige Form a gut quasi ordnen.[35][33]
- 2009:
- Maria Chudnovsky, Neil Robertson, Paul Seymour und Robin Thomas, für die starker perfekter Diagrammsatz.[36][37]
- Daniel A. Spielman und Shang-Hua Teng, zum Geglättete Analyse von Lineares Programmieren Algorithmen.[38][37]
- Thomas C. Hales und Samuel P. Ferguson, um das zu beweisen Kepler -Vermutung auf dem dichtesten möglich Kugelpackungen.[39][40][37]
- 2012:
- Sanjeev Arora, Satish Rao, und Umesh Vazirani zur Verbesserung der Annäherungsverhältnis zum Grafikabscheider und verwandte Probleme von zu .[41]
- Anders Johansson, Jeff Kahn, und Van H. Vu zur Bestimmung der Schwelle der Kantendichte, über dem a Zufällige Grafik Kann durch disjunkte Kopien eines bestimmten kleineren Diagramms abgedeckt werden.[42]
- László Lovász und Balázs Szegedy zur Charakterisierung der Subgraph -Multiplizität in Sequenzen von dichte Grafiken.[43]
- 2015:
- Francisco Santos Leal zum ein Gegenbeispiel der Hirsch -Vermutung.[44][45]
- 2018:
- Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen und Julia Böttcher für Die chromatischen Schwellenwerte von Graphen
- Thomas Rothvoss für seine Arbeit am Erweiterungskomplexität des passendes Polytope.[46]
- 2021:
- Béla csaba, Daniela Kühn, Allan Lo, Deryk Osthusund Andrew Treglown für Nachweis der 1-Faktorisierung und Hamilton-Zersetzung Vermutungen
- Jin-yi Cai und Xi Chen zum Komplexität des Zählens von CSP mit komplexen Gewichten
- Ken-ichi Kawarabayashi und Mikkel Thorup zum Deterministische Kantenkonnektivität in nahezu linearer Zeit
Siehe auch
Verweise
- ^ Karp, Richard M. (1975). "Über die rechnerische Komplexität kombinatorischer Probleme". Netzwerke. 5: 45–68. doi:10.1002/net.1975.5.1.45.
- ^ Appel, Kenneth; Haken, Wolfgang (1977). "Jede planare Karte ist vier farbig, Teil I: Entladung". Illinois Journal of Mathematics. 21: 429–490.
- ^ Seymour, Paul (1977). "Die Matroiden mit der max-Flus-Min-Cut-Eigenschaft". Journal of Combinatorial Theory. 23: 189–222. doi:10.1016/0095-8956 (77) 90031-4.
- ^ Judin, D.B.; Nemirovski, Arkadi (1976). "Informationskomplexität und wirksame Lösungsmethoden für konvexe extreme Probleme". Ekonomika I Matematicheskie Metody. 12: 357–369.
- ^ Khachiyan, Leonid (1979). "Ein Polynomalgorithmus in der linearen Programmierung". Akademiia Nauk SSSR. Doklady. 244: 1093–1096.
- ^ "Leonid Khachiyan, Professor, führender Informatiker". Boston Globe. 5. Mai 2005..
- ^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1981). "Die Ellipsoid -Methode und ihre Konsequenzen in der kombinatorischen Optimierung". Combinatorica. 1: 169–197. doi:10.1007/bf02579273.
- ^ Egorychev, G. P. (1981). "Die Lösung von Van der Waerdens Problem für Permanents". Akademiia Nauk SSSR. Doklady. 258: 1041–1044.
- ^ Falikman, D. I. (1981). "Ein Beweis für die Van der Waerden -Vermutung auf der Permanent einer doppelt stochastischen Matrix". Matematicheskie Zametki. 29: 931–938.
- ^ Beck, Jozsef (1981). "Roths Schätzung der Diskrepanz von Ganzzahlsequenzen ist nahezu scharf". Combinatorica. 1 (4): 319–325. doi:10.1007/bf02579452.
- ^ Lenstra, H. W.; JR (1983). "Ganzzahlprogrammierung mit einer festen Anzahl von Variablen". Mathematics of Operations Research. 8 (4): 538–548. Citeseerx 10.1.1.431.5444. doi:10.1287/moor.8.4.538.
- ^ Luks, Eugene M. (1982). "Der Isomorphismus von Graphen der begrenzten Valenz kann in der Polynomzeit getestet werden". Journal of Computer and System Sciences. 25 (1): 42–65. doi:10.1016/0022-0000 (82) 90009-5.
- ^ "U of O Computer Chief erhält die Top -Auszeichnung". Eugene Register-Guard. 10. August 1985..
- ^ TARDOS, ÉVA (1985). "Ein stark polynomialer Mindestkostenkreislaufalgorithmus". Combinatorica. 5: 247–256. doi:10.1007/bf02579369.
- ^ Karmarkar, Narendra (1984). "Ein neuer Polynom-Zeit-Algorithmus für die lineare Programmierung". Combinatorica. 4: 373–395. doi:10.1007/bf02579150.
- ^ Dyer, Martin E.; Frieze, Alan M.; Kannan, Ravindran (1991). "Ein zufälliger Polynomzeitalgorithmus zur Annäherung an das Volumen der konvexen Körper". Journal of the ACM. 38 (1): 1–17. Citeseerx 10.1.1.145.4600. doi:10.1145/102782.102783.
- ^ Alfred Lehman, "Die Breitelänge-Ungleichheit und entartete Projektivflugzeuge", W. Cook und P. D. Seymour (Hrsg.), Polyedrale Kombinatorik, Dimacs-Serie in diskreter Mathematik und theoretische Informatik, Band 1, (American Mathematical Society, 1990) ppp . 101-105.
- ^ Nikolai E. MNEV, "Die Universalitätstheoreme zum Klassifizierungsproblem von Konfigurationssorten und konvexen Polytopensorten", O. Ya. Viro (Hrsg.), Topology and Geometry-Rohlin Seminar, Vorlesungsnotizen in Mathematik 1346 (Springer-Verlag, Berlin, 1988) S. 527-544.
- ^ Bilera, Louis (1988). "Homologie von glatten Splines: Generische Triangulationen und eine Vermutung von Strang". Transaktionen der American Mathematical Society. 310: 325–340. doi:10.2307/2001125.
- ^ Kalai, Gil (1992). "Obergrenzen für den Durchmesser und die Höhe der Graphen der konvexen Polyeder". Diskrete und rechnerische Geometrie. 8: 363–372. doi:10.1007/bf02293053.
- ^ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). "Hadwigers Vermutung für K_6-freie Grafiken". Combinatorica. 13: 279–361. doi:10.1007/bf01202354.
- ^ Kim, Jeong Han (1995). "Die Ramsey -Nummer R(3,t) hat Größenordnung t2/Protokollt". Zufällige Strukturen und Algorithmen. 7 (3): 173–207. doi:10.1002/RSA.3240070302. HERR 1369063..
- ^ Goemans, Michel X.; Williamson, David P. (1995). "Verbesserte Approximationsalgorithmen für die maximale Schnitt- und Erlfdigungsversorgung probelsm unter Verwendung einer semi-definitischen Programmierung". Journal of the ACM. 42 (6): 1115–1145. doi:10.1145/227683.227684.
- ^ Michele corti, Gérard Cornuéjols und M. R. Rao, "Zersetzung ausgewogener Matrizen", Journal of Combinatorial Theory, Serie B, 77 (2): 292–406, 1999.
- ^ "Herr Rao neuer Dekan von ISB". Financial Express. 2. Juli 2004..
- ^ J. F. Geelen, A. M. H. Gerards und A. Kapoor, "Die ausgeschlossenen Minderjährigen für GF (4) -repräsentierbare Matroiden," Journal of Combinatorial Theory, Serie B, 79 (2): 247–2999, 2000.
- ^ a b c 2003 Fulkerson -Preiszitat, abgerufen 2012-08-18.
- ^ Bertrand Guenin, "Eine Charakterisierung schwach zweipartnerer Graphen", " Journal of Combinatorial Theory, Serie B, 83 (1): 112–168, 2001.
- ^ Satoru Iwata, Lisa Fleischer, Satoru Fujishige, "Ein kombinatorischer starker Polynomalgorithmus zur Minimierung von Submodularfunktionen", Journal of the ACM48 (4): 761–777, 2001.
- ^ Alexander Schrijver"Ein kombinatorischer Algorithmus minimiert submoduläre Funktionen in stark polynomialen Zeit", " Journal of Combinatorial Theory, Series B 80 (2): 346–355, 2000.
- ^ Manindra Agrawal, Neeraj Kayal und Nitin Saxena"Primes ist in p", " Annalen der Mathematik, 160 (2): 781–793, 2004.
- ^ Raghunathan, M. S. (11. Juni 2009). "Indien als Spieler in Mathematik". Der Hindu. Archiviert von das Original am 14. Juni 2009..
- ^ a b c 2006 Fulkerson -Preiszitat, abgerufen 2012-08-19.
- ^ Mark Jerrum, Alistair Sinclair und Eric Vigoda, "ein Polynom-Zeit-Annäherungsalgorithmus für die Permanent einer Matrix mit nichtnegativen Einträgen", " Journal of the ACM, 51 (4): 671–697, 2004.
- ^ Neil Robertson und Paul Seymour"Graph Minderjährige. Xx. Wagners Vermutung", " Journal of Combinatorial Theory, Serie B, 92 (2): 325–357, 2004.
- ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "Der starke perfekte Graph -Theorem". Annalen der Mathematik. 164: 51–229. Arxiv:Math/0212070. doi:10.4007/Annals.2006.164.51.
- ^ a b c 2009 Fulkerson -Preiszitat, abgerufen 2012-08-19.
- ^ Spielman, Daniel A.; Teng, Shang-Hua (2004). "Geglättete Analyse von Algorithmen: Warum der Simplex -Algorithmus normalerweise die Polynomzeit benötigt". Journal of the ACM. 51: 385–463. Arxiv:Math/0212413. doi:10.1145/990308.990310.
- ^ Hales, Thomas C. (2005). "Ein Beweis der Kepler -Vermutung". Annalen der Mathematik. 162: 1063–1183. doi:10.4007/Annals.2005.162.1065.
- ^ Ferguson, Samuel P. (2006). "Kugelpackungen, V. Pentaedrische Prismen". Diskrete und rechnerische Geometrie. 36: 167–204. doi:10.1007/s00454-005-1214-y.
- ^ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander fließt, geometrische Einbettungen und Grafikpartitionierung". Journal of the ACM. 56: 1–37. Citeseerx 10.1.1.310.2258. doi:10.1145/1502793.1502794.
- ^ Johansson, Anders; Kahn, Jeff; Vu, Van H. (2008). "Faktoren in zufälligen Grafiken". Zufällige Strukturen und Algorithmen. 33: 1–28. doi:10.1002/RSA.20224.
- ^ Lovász, László; Szegedy, Balázs (2006). "Grenzen dichter Graph -Sequenzen". Journal of Combinatorial Theory. 96: 933–957. Arxiv:Math/0408173. doi:10.1016/j.jctb.2006.05.002.
- ^ Santos, Francisco (2011). "Ein Gegenbeispiel zur Hirsch -Vermutung". Annalen der Mathematik. 176 (1): 383–412. Arxiv:1006.2814. doi:10.4007/Annals.2012.176.1.7. HERR 2925387.
- ^ 2015 Fulkerson -Preiszitat, abgerufen 2015-07-18.
- ^ Rothvoß, Thomas (2017). "Das passende Polytope hat eine exponentielle Erweiterungskomplexität". Journal of the ACM. 64 (6): A41: 1 - A41: 19. Arxiv:1311.2369. doi:10.1145/3127497. HERR 3713797.