Fulkersonova cena

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. +more 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 O(\log n) do O(\sqrt{\log n}) * 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

[url=http://www. ams. +moreorg/prizes/fulkerson-prize. html]oficiální stránky[/url] (anglicky) * [url=http://www. ams. org/profession/prizes-awards/pabrowse]archiv s dřívějšími laureáty[/url] (anglicky).

Kategorie:Matematická ocenění Kategorie:Informatická ocenění