Fulkerson Prize

from Wikipedia, the free encyclopedia

The Fulkerson Prize (Delbert Ray Fulkerson Prize) is a three-year prize awarded by the Mathematical Programming Society (MPS) and the American Mathematical Society (AMS) for exceptional work in discrete mathematics, including combinatorial and computer science . Up to three prizes will be awarded, each worth $ 1,500. They are named after Delbert Ray Fulkerson and were originally financed from a fund donated by friends of Fulkerson in his memory.

Award winners

  • 1979: Richard M. Karp (for On the computational complexity of combinatorial problems , Networks, Vol. 5, 1975, pp. 45-68); Kenneth Appel and Wolfgang Haken (for the four-color set , in Every planar map is four colorable, Part I: Discharging , Illinois Journal of Mathematics, Vol. 21, 1977, pp. 429-490); Paul Seymour (for The matroids with the max-flow min-cut property , Journal of Combinatorial Theory, Series B, Vol. 23, 1977, pp. 189-222).
  • 1982: DB Judin and Arkadi Nemirovski (for Informational complexity and effective methods of solution for convex extremal problems , Ekonomika i Matematicheskie Metody, Vol. 12, 1976, pp. 357-369); Leonid Khachiyan (for A polynomial algorithm in linear programming , Akademiia Nauk SSSR. Doklady, Vol. 244, 1979, p. 1073); GP Egorychev (for The solution of van der Waerden's problem for permanents , Akademiia Nauk SSSR. Doklady, Vol. 258, 1981, pp. 1041-1044); DI Falikman (for A proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix , Matematicheskie Zametki, Vol. 29, 1981, pp. 931-938); Martin Grötschel , László Lovász and Alexander Schrijver (for The ellipsoid method and its consequences in combinatorial optimization , Combinatorica, Vol. 1, 1981, pp. 169-197).
  • 1985: József Beck (for Roth's estimate of the discrepancy of integer sequences is nearly sharp , Combinatorica, Vol. 1, 1981, pp. 319-325); Hendrik Lenstra (for integer programming with a fixed number of variables , Mathematics of Operations Research, Vol. 8, 1983, pp. 538-548); Eugene M. Luks (for Isomorphism of graphs of bounded valence can be tested in polynomial time , Journal of Computer and System Sciences, Vol. 25, 1982, pp. 42-65).
  • 1988: Éva Tardos (for A strongly polynomial minimum cost circulation algorithm , Combinatorica, Vol. 5, 1985, pp. 247-256); Narendra Karmarkar (for A new polynomial-time algorithm for linear programming , Combinatorica, Vol. 4, 1984, pp. 373-395).
  • 1991: Martin E. Dyer , Alan M. Frieze and Ravindran Kannan (for A random polynomial time algorithm for approximating the volume of convex bodies , Journal of the ACM, Vol. 38, 1991, pp. 1-17); Alfred Lehman (for The width-length inequality and degenerate projective planes , in W. Cook, PD Seymour (editor), Polyhedral Combinatorics , DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, American Mathematical Society, 1990, p. 101-105); Nikolai E. Mnev (for The universality theorems on the classification problem of configuration varieties and convex polytope varieties , in Oleg Viro (editor), Topology and Geometry-Rohlin Seminar , Lecture Notes in Mathematics Vol. 1346, Springer 1988, p. 527– 544).
  • 1994: Louis Billera (for Homology of smooth splines: Generic triangulations and a conjecture of Strang , Transactions of the AMS, Vol. 310, 1988, pp. 325-340); Gil Kalai (for Upper bounds for the diameter and height of graphs of the convex polyhedra , Discrete and Computational Geometry, Vol. 8, 1992, pp. 363-372); Neil Robertson , Paul Seymour and Robin Thomas (for Hadwiger's conjecture for K6; free graphs , Combinatorica, Vol. 13, 1993, pp. 279-361).
  • 1997: Jeong Han Kim (for The Ramsey Number R (3, t) Has Order of Magnitude t2 / log t , Random Structures and Algorithms, Vol. 7, 1995, pp. 173-207).
  • 2000: Michel X. Goemans and David P. Williamson (for Improved approximation algorithms for the maximum cut and satisfiability problems using semi-definite programming , Journal of the ACM, Vol. 42, 1995, pp. 1115-1145); Michele Conforti , Gérard Cornuéjols and MR Rao (for Decomposition of balanced matrices , Journal of Combinatorial Theory, Series B, Vol. 77, 1999, pp. 292-406).
  • 2003: JF Geelen , AMH Gerards and A. Kapoor (for The Excluded Minors for GF (4) -Representable Matroids, Journal of Combinatorial Theory Series B, Vol. 79, 2000, pp. 247-299); Bertrand Guenin (for A characterization of weakly bipartite graphs, Journal of Combinatorial Theory Series B, Vol. 83, 2001, pp. 112-168); Satoru Iwata , Lisa Fleischer , Satoru Fujishige (for A combinatorial strongly polynomial algorithm for minimizing submodular functions , Journal of the ACM, Vol. 48, 2001, pp. 761-777); Alexander Schrijver (for A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, Vol. 80, 2000, pp. 346-355).
  • 2006: Manindra Agrawal , Neeraj Kayal and Nitin Saxena (for their polynomial prime number test in "PRIMES is in P , Annals of Mathematics, vol. 160, 2004, pp. 781--793); Mark Jerrum , Alistair Sinclair and Eric Vigoda (for A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries , Journal of the ACM, Vol. 51, 2004); Neil Robertson and Paul Seymour (for Graph Minors. XX. Wagner's conjecture , Journal of Combinatorial Theory, Series B , Vol. 92, 2004, pp. 325-357).
  • 2009: Maria Chudnovsky , Neil Robertson , Paul Seymour , Robin Thomas (for The strong perfect graph theorem , Annals of Mathematics, Vol. 164, 2006, pp. 51-229); Daniel Spielman , Shang-Hua Teng (for Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time , Journal of the ACM, Vol. 51, 2004, pp. 385-463); Thomas Hales (for A proof of the Kepler conjecture , Annals of Mathematics, Vol. 162, 2005, pp. 1063-1183); Samuel P. Ferguson (for Sphere Packings, V .: Pentahedral Prisms , Discrete and Computational Geometry, Vol. 36, 2006, pp. 167-204).
  • 2012: Sanjeev Arora , Satish Rao and Umesh Vazirani (for Expander flows, geometric embeddings and graph partitioning , Journal of the ACM, Vol. 56, pp. 1-37, 2009); Anders Johansson , Jeff Kahn , and Van H. Vu (for Factors in random graphs , Random Structures and Algorithms Vol. 33, pp. 1-28, 2008); László Lovász and Balázs Szegedy (for Limits of dense graph sequences , Journal of Combinatorial Theory, Series B, Vol. 96, pp. 933–957, 2006)
  • 2015: Francisco Santos (for A Counterexample to the Hirsch Conjecture , Annals of Mathematics, 2012).
  • 2018: Thomas Rothvoss

Web links