Fulkersonova cena (v originále anglicky ) je společná cena Společnosti matematického programování (MPS) a Americké matematické společnosti (AMS). Je udělována za výjimečné články v oboru diskrétní matematiky, zejména kombinatoriky, a nese jméno Delberta Raye Fulkersona. K udělení dochází na mezinárodním sympóziu MPS, které se koná každé tři roky, a vždy jsou uděleny až tři Fulkersonovy ceny.
Laureáti
1979 Richard M. Karp za klasifikaci mnoha důležitých NP-úplných problémů. Kenneth Appel a Wolfgang Haken za vyřešení problému čtyř barev. Paul Seymour za zobecnění Fordovy-Fulkersonovy věty pro matroidy. 1982 D. B. Judin, Arkadi Nemirovski, Leonid Genrichovič Chačijan, Martin Grötschel, László Lovász a Alexander Schrijver za elipsoidovou metodu v lineárním programování a kombinatorické optimalizaci. Georgij Petrovič Jegoryčev a D. I. Falikman za důkaz van der Waerdenovy domněnky, že matice se všemi položkami stejnými má nejmenší permanent ze všech dvojitě stochastických 1985 Jozsef Beck za těsné ohraničení odchylek aritmetických posloupností Hendrik Lenstra za využití geometrie čísel k vyřešení celočíselných programů s málo neznámými v čase polynomiálním vzhledem k počtu omezujících podmínek. Eugene M. Luks za polynomiální algoritmus k řešení problému grafových isomorfismů pro grafy s omezeným maximálním stupněm vrcholu. 1988 Éva Tardosová za silně polynomiální algoritmus pro řešení problému minimalizačního problému cirkulace Narendra Karmarkar za Karmarkarův algoritmus v lineárním programování 1991 Martin Dyer, Alan M. Frieze a Ravindram Kannan za aproximační algoritmus pro výpočet objemu konvexních těles založený na náhodné procházce. Alfred Lehman pro analogii k teorii perfektních grafů pro 0,1-matice. Nikolaj Jevgeňjevič Mňov za Mňovovu větu o univerzalitě, podle které je každá poloalgebraická množina ekvivalentní prostoru realizací orientovaného matroidu. 1994 Louis Billera za nalezení bází po částech polynomiálních prostorů funkcí nad triangulacemi prostoru. Gil Kalai za pokrok v rozhodování Hirschovy domněnky Neil Robertson, Paul Seymour a Robin Thomas za šestibarevný případ Hadwigerovy domněnky. 1997 Kim Džŏnghan za nalezení asymptotické rychlosti růstu Ramseyových čísel R(3, t). 2000 Michel Goemans a David P. Williamson za aproximační algoritmy založené na semidefinitním programování Michele Conforti, Gérard Cornuéjols a Mendu Rao za rozpoznávání vyvážených logických matic v polynomiálním čase. 2003 Jim Geelen, A. M. H. Gerards a A. Kapoor za případ Rotovy domněnky na matroidových minorech pro případ GF(4). Bertrand Guenin za zakázanou minorovou charakterizaci slabě bipartitních grafů Satoru Iwata, Lisa Fleischerová, Satoru Fudžišige a Alexander Schrijver 2006 Maníndra Agravál, Níradž Kajál a Nitin Saxena za Agraválův-Kajálův-Saxenův test prvočíselnosti Mark Jerrum, Alistair Sinclair a Eric Vigoda za aproximování permanentu Neil Robertson a Paul Seymour za Robertsonovu-Seymourovu větu, která ukazuje, že minory grafu tvoří dobré kvaziuspořádání. 2009 Maria Chudnovsky, Neil Robertson, Paul Seymour a Robin Thomas za větu o silně perfektních grafech. Daniel A. Spielman a Shang-Hua Teng, za hladkou analýzu algoritmu lineárního programování. Thomas C. Hales a Samuel P. Ferguson za důkaz Keplerovy domněnky o nejhustším možném poskládání koulí. 2012 Sanjeev Arora, Satish Rao a Umesh Vazirani za důkaz aproximačního poměru pro grafové oddělovače a příbuzné problémy od do Anders Johansson, Jeff Kahn a Vũ Hà Văn za určení prahu hraniční hustoty, nad kterou může být náhodný graf pokryt disjunktními kopie daného menšího grafu. László Lovász a Balázs Szegedy za charakterizaci násobnosti podgrafů v posloupnostech hustých grafů. 2015 Francisco Santos Leal za protipříklad Hirschovy domněnky. 2018 Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen a Julia Böttcher za článek The chromatic thresholds of graphs Thomas Rothvoss za článek The Matching Polytope has Exponential Extension Complexity
Odkazy Reference
Externí odkazy oficiální stránky (anglicky) archiv s dřívějšími laureáty (anglicky)
Kategorie:Vzniklo 1979 Kategorie:Matematická ocenění Kategorie:Informatická ocenění