Fulkerson-Preis

Der Fulkerson-Preis (Delbert Ray Fulkerson Prize) ist ein von der Mathematical Programming Society (MPS) und der American Mathematical Society (AMS) alle drei Jahre vergebener Preis für außergewöhnliche Arbeiten in diskreter Mathematik, worunter zum Beispiel Kombinatorik und Informatik fallen. Es werden bis zu drei Preise verliehen, dotiert mit jeweils 1500 Dollar. Sie sind nach Delbert Ray Fulkerson benannt und waren ursprünglich aus einem Fonds finanziert, den Freunde von Fulkerson in seinem Andenken stifteten.

Preisträger

  • 1979: Richard M. Karp (für On the computational complexity of combinatorial problems, Networks, Bd. 5, 1975, S. 45–68); Kenneth Appel und Wolfgang Haken (für den Vier-Farben-Satz, in Every planar map is four colorable, Part I: Discharging, Illinois Journal of Mathematics, Bd. 21, 1977, S. 429–490); Paul Seymour (für The matroids with the max-flow min-cut property, Journal of Combinatorial Theory, Series B, Bd. 23, 1977, S. 189–222).
  • 1982: D. B. Judin und Arkadi Nemirovski (für Informational complexity and effective methods of solution for convex extremal problems, Ekonomika i Matematicheskie Metody, Bd. 12, 1976, S. 357–369); Leonid Khachiyan (für A polynomial algorithm in linear programming, Akademiia Nauk SSSR. Doklady, Bd. 244, 1979, S. 1073); G. P. Egorychev (für The solution of van der Waerden’s problem for permanents, Akademiia Nauk SSSR. Doklady, Bd. 258, 1981, S. 1041–1044); D. I. Falikman (für A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Matematicheskie Zametki, Bd. 29, 1981, S. 931–938); Martin Grötschel, László Lovász und Alexander Schrijver (für The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, Bd. 1, 1981, S. 169–197).
  • 1985: József Beck (für Roth’s estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica, Bd. 1, 1981, S. 319–325); Hendrik Lenstra (für Integer programming with a fixed number of variables, Mathematics of Operations Research, Bd. 8, 1983, S. 538–548); Eugene M. Luks (für Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences, Bd. 25, 1982, S. 42–65).
  • 1988: Éva Tardos (für A strongly polynomial minimum cost circulation algorithm, Combinatorica, Bd. 5, 1985, S. 247–256); Narendra Karmarkar (für A new polynomial-time algorithm for linear programming, Combinatorica, Bd. 4, 1984, S. 373–395).
  • 1991: Martin E. Dyer, Alan M. Frieze und Ravindran Kannan (für A random polynomial time algorithm for approximating the volume of convex bodies, Journal of the ACM, Bd. 38, 1991, S. 1–17); Alfred Lehman (für The width-length inequality and degenerate projective planes, in W. Cook, P. D. Seymour (Herausgeber), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Bd. 1, American Mathematical Society, 1990, S. 101–105); Nikolai E. Mnev (für The universality theorems on the classification problem of configuration varieties and convex polytope varieties, in Oleg Viro (Herausgeber), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics Bd. 1346, Springer 1988, S. 527–544).
  • 1994: Louis Billera (für Homology of smooth splines: Generic triangulations and a conjecture of Strang, Transactions of the AMS, Bd. 310, 1988, S. 325–340); Gil Kalai (für Upper bounds for the diameter and height of graphs of the convex polyhedra, Discrete and Computational Geometry, Bd. 8, 1992, S. 363–372); Neil Robertson, Paul Seymour und Robin Thomas (für Hadwiger’s conjecture for K6; free graphs, Combinatorica, Bd. 13, 1993, S. 279–361).
  • 1997: Jeong Han Kim (für The Ramsey Number R(3,t) Has Order of Magnitude t2/log t, Random Structures and Algorithms, Bd. 7, 1995, S. 173–207).
  • 2000: Michel X. Goemans und David P. Williamson (für Improved approximation algorithms for the maximum cut and satisfiability problems using semi-definite programming, Journal of the ACM, Bd. 42, 1995, S. 1115–1145); Michele Conforti, Gérard Cornuéjols und M. R. Rao (für Decomposition of balanced matrices, Journal of Combinatorial Theory, Series B, Bd. 77, 1999, S. 292–406).
  • 2003: J. F. Geelen, A. M. H. Gerards und A. Kapoor (für The Excluded Minors for GF(4)-Representable Matroids,Journal of Combinatorial Theory Series B, Bd. 79, 2000, S. 247–299); Bertrand Guenin (für A characterization of weakly bipartite graphs, Journal of Combinatorial Theory Series B, Bd. 83, 2001, S. 112–168); Satoru Iwata, Lisa Fleischer, Satoru Fujishige (für A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, Bd. 48, 2001, S. 761–777); Alexander Schrijver (für A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, Bd. 80, 2000, S. 346–355).
  • 2006: Manindra Agrawal, Neeraj Kayal und Nitin Saxena (für ihren polynomialen Primzahltest in "PRIMES is in P, Annals of Mathematics, Bd. 160, 2004, S. 781–793); Mark Jerrum, Alistair Sinclair und Eric Vigoda (für A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM, Bd. 51, 2004); Neil Robertson und Paul Seymour (für Graph Minors. XX. Wagner’s conjecture, Journal of Combinatorial Theory, Series B, Bd. 92, 2004, S. 325–357).
  • 2009: Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas (für The strong perfect graph theorem, Annals of Mathematics, Bd. 164, 2006, S. 51–229); Daniel Spielman, Shang-Hua Teng (für Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM, Bd. 51, 2004, S. 385–463); Thomas Hales (für A proof of the Kepler conjecture, Annals of Mathematics, Bd. 162, 2005, S. 1063–1183); Samuel P. Ferguson (für Sphere Packings, V.: Pentahedral Prisms, Discrete and Computational Geometry, Bd. 36, 2006, S. 167–204).
  • 2012: Sanjeev Arora, Satish Rao und Umesh Vazirani (für Expander flows, geometric embeddings and graph partitioning, Journal of the ACM, Bd. 56, S. 1–37, 2009); Anders Johansson, Jeff Kahn, und Van H. Vu (für Factors in random graphs, Random Structures and Algorithms Bd. 33, S. 1–28, 2008); László Lovász und Balázs Szegedy (für Limits of dense graph sequences, Journal of Combinatorial Theory, Serie B, Bd. 96, S. 933–957, 2006)
  • 2015: Francisco Santos (für A Counterexample to the Hirsch Conjecture, Annals of Mathematics, 2012).
  • 2018: Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert Morris (für The chromatic thresholds of graphs, Advances in Mathematics, Bd. 235, S. 261–295, 2013); Thomas Rothvoß (für The Matching Polytope has Exponential Extension Complexity, Journal of the ACM, Bd. 64 S. 1–19, 2017).
  • 2021: Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus, Andrew Treglown: Proof of the 1-factorization and Hamilton Decomposition Conjectures. In: Memoirs of the American Mathematical Society. 244, 2016, S. 0, doi:10.1090/memo/1154; Jin-Yi Cai, Xi Chen: Complexity of Counting CSP with Complex Weights. In: Journal of the ACM. 64, 2017, S. 1, doi:10.1145/2822891; Ken-Ichi Kawarabayashi, Mikkel Thorup: Deterministic Edge Connectivity in Near-Linear Time. In: Journal of the ACM. 66, 2019, S. 1, doi:10.1145/3274663.[1]
  • 2024: Ben Cousins and Santosh Vempala: Gaussian Cooling and O*(n3) Algorithms for Volume and Gaussian Volume, published in SIAM Journal on Computing in 2018; Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao: Equiangular lines with a fixed angle, published in Annals of Mathematics in 2021; Nathan Keller and Noam Lifshitz: The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture, published in Advances in Mathematics in 2021.[2]

Einzelnachweise

  1. ↑ The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by @math_opt and @amermathsoc. In: twitter.com. 22. Juli 2021, abgerufen am 24. Juli 2021.
  2. ↑ Laureates 2024