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.

Lauerá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 $0(\log n)$ do $0({\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ů.

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 laueráty (anglicky)