Fulkersonova cena - Fulkerson Prize
| Fulkersonova cena | |
|---|---|
| Oceněn pro | Vynikající příspěvky v oblasti diskrétní matematika |
| Země | Spojené státy |
| Předložený | Společnost pro matematickou optimalizaci Americká matematická společnost |
| Odměna | $1,500 |
| Poprvé oceněn | 1979 |
| webová stránka | http://www.ams.org/profession/prizes-awards/ams-prizes/fulkerson-prize  |
The Fulkersonova cena za vynikající příspěvky v oblasti diskrétní matematika je společně sponzorováno Společnost pro matematickou optimalizaci (MOS) a Americká matematická společnost (AMS). Na každém (tříletém) mezinárodním sympoziu USA se udělují až tři ocenění, každý po 1 500 $ MOS. Ceny byly původně vypláceny z pamětního fondu spravovaného AMS, který založili přátelé zesnulého Delbert Ray Fulkerson podporovat matematickou dokonalost v oblastech výzkumu ilustrovaných jeho prací. Ceny jsou nyní financovány z nadace spravované MPS.
Vítězové
Zdroj: Společnost pro matematickou optimalizaci
- 1979:
- Richard M. Karp pro klasifikaci mnoha důležitých NP-kompletní problémy.[1]
- Kenneth Appel a Wolfgang Haken pro čtyřbarevná věta.[2]
- Paul Seymour pro zobecnění věta o maximálním toku o minimálním řezu na matroidy.[3]
- 1982:
- D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grötschel, László Lovász a Alexander Schrijver pro elipsoidní metoda v lineární programování a kombinatorická optimalizace.[4][5][6][7]
- G. P. Egorychev a D. I. Falikman za prokázání van der Waerden Domněnka, že matice se všemi stejnými položkami má nejmenší trvalý ze všech dvojnásobně stochastická matice.[8][9]
- 1985:
- Jozsef Beck pro pevné hranice na rozpor z aritmetické průběhy.[10]
- H. W. Lenstra, Jr. pro použití geometrie čísel vyřešit celočíselné programy s několika proměnnými v časovém polynomu v počtu omezení.[11]
- Eugene M. Luks pro polynomiální čas algoritmus izomorfismu grafu pro grafy ohraničené maximální stupeň.[12][13]
- 1988:
- 1991:
- Martin E. Dyer, Alan M. Frieze a Ravindran Kannan pro náhodná procházka -na základě aproximační algoritmy pro objem konvexních těl.[16]
- Alfred Lehman pro 0,1 matice analogy teorie perfektní grafy.[17]
- Nikolai E. Mnev pro Mnevova věta o univerzálnosti, že každá semialgebraická množina je ekvivalentní prostoru realizace an orientovaný matroid.[18]
- 1994:
- Louis Billera pro hledání základů funkčních prostorů po částech a polynomech nad triangulacemi prostoru.[19]
- Gil Kalai za pokrok na internetu Hirschova domněnka prokázáním subexponenciálních mezí na průměru d-rozměrné polytopy s n fazety.[20]
- Neil Robertson, Paul Seymour a Robin Thomas pro šestibarvové pouzdro Hadwigerova domněnka.[21]
- 1997:
- Jeong Han Kim pro nalezení rychlost asymptotického růstu z Ramseyova čísla R(3,t).[22]
- 2000:
- Michel X. Goemans a David P. Williamson pro aproximační algoritmy na základě semidefinitní programování.[23]
- Michele Conforti, Gérard Cornuéjols, a M. R. Rao za poznání vyvážené matice 0-1 v polynomiální čas.[24][25]
- 2003:
- J. F. Geelen, A. M. H. Gerards a A. Kapoor pro GF (4) případ Rotaova domněnka na matroidní nezletilí.[26][27]
- Bertrand Guenin pro a zakázaná drobná charakterizace slabě bipartitních grafů (grafy, jejichž bipartitní subgrafový polytop je 0-1).[28][27]
- Satoru Iwata, Lisa Fleischer, Satoru Fujishige a Alexander Schrijver pro předvádění submodulární minimalizace být silně polynomický.[29][30][27]
- 2006:
- Manindra Agrawal, Neeraj Kayal a Nitin Saxena, pro Test prvosti AKS.[31][32][33]
- Mark Jerrum, Alistair Sinclair a Eric Vigoda pro aproximovat trvalé.[34][33]
- Neil Robertson a Paul Seymour, pro Věta Robertson – Seymour což ukazuje nezletilí v grafu formulář a dobře kvazi-objednávání.[35][33]
- 2009:
- Maria Chudnovsky, Neil Robertson, Paul Seymour a Robin Thomas pro silná dokonalá věta o grafu.[36][37]
- Daniel A. Spielman a Shang-Hua Teng, pro uhlazená analýza z lineární programování algoritmy.[38][37]
- Thomas C. Hales a Samuelovi P. Fergusonovi za prokázání Keplerova domněnka na nejhustší možné koule balení.[39][40][37]
- 2012:
- Sanjeev Arora, Satish Rao a Umesh Vazirani pro zlepšení přibližný poměr pro oddělovače grafů a související problémy z na .[41]
- Anders Johansson, Jeff Kahn, a Van H. Vu pro stanovení prahu hustoty okraje, nad kterou a náhodný graf mohou být pokryty disjunktními kopiemi daného menšího grafu.[42]
- László Lovász a Balázs Szegedy pro charakterizaci multiplicity podgrafu v sekvencích husté grafy.[43]
- 2015:
- Francisco Santos Leal pro protiklad příkladu Hirschova domněnka.[44][45]
- 2018:
- Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen a Julia Böttcher pro Chromatické prahové hodnoty grafů
- Thomas Rothvoss pro Odpovídající Polytop má složitost exponenciálního rozšíření
Viz také
Reference
- ^ Karp, Richard M. (1975). „O výpočetní složitosti kombinatorických problémů“. Sítě. 5: 45–68. doi:10,1002 / net.1975.5.1.45.
- ^ Appel, Kenneth; Haken, Wolfgang (1977). „Každá planární mapa je čtyřbarevná, část I: Vybíjení“. Illinois Journal of Mathematics. 21: 429–490.
- ^ Seymour, Paule (1977). "Matroidy s vlastností min-cut max-flow". Journal of Combinatorial Theory. 23: 189–222. doi:10.1016/0095-8956(77)90031-4.
- ^ Judin, D.B .; Nemirovski, Arkadi (1976). "Informační složitost a efektivní metody řešení konvexních extrémních problémů". Ekonomika i Matematicheskie Metody. 12: 357–369.
- ^ Khachiyan, Leonid (1979). Msgstr "Polynomiální algoritmus v lineárním programování". Akademiia Nauk SSSR. Doklady. 244: 1093–1096.
- ^ „Leonid Khachiyan, profesor, přední počítačový vědec“, Boston Globe, 5. května 2005.
- ^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1981). "Elipsoidní metoda a její důsledky v kombinatorické optimalizaci". Combinatorica. 1: 169–197. doi:10.1007 / bf02579273.
- ^ Egorychev, G. P. (1981). „Řešení van der Waerdenova problému pro stálé zaměstnance“. Akademiia Nauk SSSR. Doklady. 258: 1041–1044.
- ^ Falikman, D. I. (1981). „Důkaz van der Waerdenova domněnky o permanentu dvojnásobně stochastické matice“. Matematicheskie Zametki. 29: 931–938.
- ^ Beck, Jozsef (1981). „Rothův odhad nesrovnalosti celočíselných sekvencí je téměř ostrý“. Combinatorica. 1 (4): 319–325. doi:10.1007 / bf02579452.
- ^ Lenstra, H. W.; Jr (1983). "Celočíselné programování s pevným počtem proměnných". Matematika operačního výzkumu. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10,1287 / bř. 8.4.538.
- ^ Luks, Eugene M. (1982). „Izomorfismus grafů ohraničené valence lze testovat v polynomiálním čase“. Journal of Computer and System Sciences. 25 (1): 42–65. doi:10.1016/0022-0000(82)90009-5.
- ^ „U of O Computer Chief získává nejvyšší ocenění“, Eugene Register-Guard, 10. srpna 1985.
- ^ Tardos, Éva (1985). Msgstr "Algoritmus cirkulace minimálních nákladů na minimální náklady". Combinatorica. 5: 247–256. doi:10.1007 / bf02579369.
- ^ Karmarkar, Narendra (1984). "Nový algoritmus polynomiálního času pro lineární programování". Combinatorica. 4: 373–395. doi:10.1007 / bf02579150.
- ^ Dyer, Martin E.; Frieze, Alan M.; Kannan, Ravindran (1991). Msgstr "Náhodný polynomiální časový algoritmus pro přiblížení objemu konvexních těles". Deník ACM. 38 (1): 1–17. CiteSeerX 10.1.1.145.4600. doi:10.1145/102782.102783.
- ^ Alfred Lehman, "Nerovnost šířky a délky projektovaných rovin," W. Cook a PD Seymour (ed.), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, svazek 1, (American Mathematical Society, 1990) 101-105.
- ^ Nikolai E. Mnev, „Věty o univerzálnosti problému klasifikace konfiguračních odrůd a konvexních odrůd polytopů,“ O. Ya. Viro, ed., Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346 (Springer-Verlag, Berlin, 1988), str. 527-544.
- ^ Billera, Louis (1988). „Homologie hladkých splajnů: Generické triangulace a domněnka o Strangovi“. Transakce Americké matematické společnosti. 310: 325–340. doi:10.2307/2001125.
- ^ Kalai, Gil (1992). "Horní hranice pro průměr a výšku grafů konvexní mnohostěny". Diskrétní a výpočetní geometrie. 8: 363–372. doi:10.1007 / bf02293053.
- ^ Robertson, Neil; Seymour, Paule; Thomas, Robin (1993). "Hadwigerova domněnka pro grafy bez K_6". Combinatorica. 13: 279–361. doi:10.1007 / bf01202354.
- ^ Kim, Jeong Han (1995), „Ramseyovo číslo R(3,t) má řádovou velikost t2/ logt", Náhodné struktury a algoritmy, 7 (3): 173–207, doi:10.1002 / rsa.3240070302, PAN 1369063.
- ^ Goemans, Michel X .; Williamson, David P. (1995). Msgstr "Vylepšené algoritmy aproximace pro maximální pravděpodobnost řezu a uspokojivosti pomocí semi-definitního programování". Deník ACM. 42 (6): 1115–1145. doi:10.1145/227683.227684.
- ^ Michele Conforti, Gérard Cornuéjols a M. R. Rao, "Rozklad vyvážených matic", Journal of Combinatorial Theory, Série B, 77 (2): 292–406, 1999.
- ^ „MR Rao, nový děkan ISB“, Finanční expres, 2. července 2004.
- ^ J. F. Geelen, A. M. H. Gerards a A. Kapoor, „Vyloučení nezletilí pro zastupující matroidy GF (4)“ Journal of Combinatorial Theory, Série B, 79 (2): 247–2 999, 2000.
- ^ A b C Citace ceny Fulkerson 2003, vyvoláno 2012-08-18.
- ^ Bertrand Guenin, „Charakterizace slabě bipartitních grafů,“ Journal of Combinatorial Theory, Série B, 83 (1): 112–168, 2001.
- ^ Satoru Iwata, Lisa Fleischerová, Satoru Fujishige, „Kombinační silně polynomický algoritmus pro minimalizaci submodulárních funkcí,“ Deník ACM, 48 (4): 761–777, 2001.
- ^ Alexander Schrijver „Kombinatorický algoritmus minimalizující submodulární funkce v silně polynomiálním čase,“ Journal of Combinatorial Theory, Série B 80 (2): 346–355, 2000.
- ^ Manindra Agrawal, Neeraj Kayal a Nitin Saxena „PRIMES je v P,“ Annals of Mathematics, 160 (2): 781–793, 2004.
- ^ Raghunathan, M. S. (11. června 2009), „Indie jako hráč v matematice“, Hind.
- ^ A b C Citace Fulkersonovy ceny 2006, vyvoláno 2012-08-19.
- ^ Mark Jerrum, Alistair Sinclair a Eric Vigoda, "Algoritmus aproximace v polynomiálním čase pro trvalou matici s nezápornými položkami," Deník ACM, 51 (4): 671–697, 2004.
- ^ Neil Robertson a Paul Seymour „Graph Minors. XX. Wagner's dohad,“ Journal of Combinatorial Theory, Série B, 92 (2): 325–357, 2004.
- ^ Chudnovský, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "Silná dokonalá věta o grafu". Annals of Mathematics. 164: 51–229. arXiv:matematika / 0212070. doi:10.4007 / annals.2006.164.51.
- ^ A b C Citace Fulkersonovy ceny za rok 2009, vyvoláno 2012-08-19.
- ^ Spielman, Daniel A.; Teng, Shang-Hua (2004). "Vyhlazená analýza algoritmů: Proč simplexní algoritmus obvykle trvá polynomiální čas". Deník ACM. 51: 385–463. arXiv:matematika / 0212413. doi:10.1145/990308.990310.
- ^ Hales, Thomas C. (2005). „Důkaz domněnky Keplera“. Annals of Mathematics. 162: 1063–1183. doi:10.4007 / annals.2005.162.1065.
- ^ Ferguson, Samuel P. (2006). „Balení koulí, V. Pentahedrální hranoly“. Diskrétní a výpočetní geometrie. 36: 167–204. doi:10.1007 / s00454-005-1214-r.
- ^ Arora, Sanjeev; Rao, satish; Vazirani, Umesh (2009). Msgstr "Toky expandéru, geometrické vložení a rozdělení grafů". Deník ACM. 56: 1–37. CiteSeerX 10.1.1.310.2258. doi:10.1145/1502793.1502794.
- ^ Johansson, Anders; Kahn, Jeff; Vu, Van H. (2008). "Faktory v náhodných grafech". Náhodné struktury a algoritmy. 33: 1–28. doi:10.1002 / rsa.20224.
- ^ Lovász, László; Szegedy, Balázs (2006). "Meze hustých sekvencí grafů". Journal of Combinatorial Theory. 96: 933–957. arXiv:matematika / 0408173. doi:10.1016 / j.jctb.2006.05.002.
- ^ Santos, Francisco (2011), „Protiklad k Hirschově domněnce“, Annals of Mathematics, 176 (1): 383–412, arXiv:1006.2814, doi:10.4007 / annals.2012.176.1.7, PAN 2925387
- ^ Citace ceny Fulkerson za rok 2015, vyvoláno 2015-07-18.