# Fulkerson Prize

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