Fulkersonova cena

Fulkersonova cena (v originále anglicky Delbert Ray Fulkerson Prize) 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 $O(\log <!--\; \; -->n)$ do $O\left(\sqrt{\log <!--\; \; -->n}\right)$
• 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

V tomto článku byly použity překlady textů z článků Fulkerson Prize na anglické Wikipedii a Премия Фалкерсона na ruské Wikipedii.

Externí odkazy

• oficiální stránky (anglicky)
• archiv s dřívějšími laureáty (anglicky)