Fulkerson Prize

Winners

• 1979:
• * Richard M. Karp for classifying many important NP-complete problems.
• * Kenneth Appel and Wolfgang Haken for the four color theorem.
• * Paul Seymour for generalizing the max-flow min-cut theorem to matroids.
• 1982:
• * D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grötschel, László Lovász and Alexander Schrijver for the ellipsoid method in linear programming and combinatorial optimization.
• *G. P. Egorychev and D. I. Falikman for proving van der Waerden's conjecture that the matrix with all entries equal has the smallest permanent of any doubly stochastic matrix.
• *
• 1985:
• * Jozsef Beck for tight bounds on the discrepancy of arithmetic progressions.
• * H. W. Lenstra, Jr. for using the geometry of numbers to solve integer programs with few variables in time polynomial in the number of constraints.
• * Eugene M. Luks for a polynomial time graph isomorphism algorithm for graphs of bounded maximum degree.
• 1988:
• * Éva Tardos for finding minimum cost circulations in strongly polynomial time.
• * Narendra Karmarkar for Karmarkar's algorithm for linear programming.
• 1991:
• * Martin E. Dyer, Alan M. Frieze and Ravindran Kannan for random-walk-based approximation algorithms for the volume of convex bodies.
• * Alfred Lehman for 0,1-matrix analogues of the theory of perfect graphs.
• * Nikolai E. Mnev for Mnev's universality theorem, that every semialgebraic set is equivalent to the space of realizations of an oriented matroid.
• 1994:
• * Louis Billera for finding bases of piecewise-polynomial function spaces over triangulations of space.
• * Gil Kalai for making progress on the Hirsch conjecture by proving subexponential bounds on the diameter of d-dimensional polytopes with n facets.
• * Neil Robertson, Paul Seymour and Robin Thomas for the six-color case of Hadwiger's conjecture.
• 1997:
• *Jeong Han Kim for finding the asymptotic growth rate of the Ramsey numbers R.
• 2000:
• * Michel X. Goemans and David P. Williamson for approximation algorithms based on semidefinite programming.
• * Michele Conforti, Gérard Cornuéjols, and M. R. Rao for recognizing balanced 0-1 matrices in polynomial time.
• 2003:
• * J. F. Geelen, A. M. H. Gerards and A. Kapoor for the GF case of Rota's conjecture on matroid minors.
• * Bertrand Guenin for a forbidden minor characterization of the weakly bipartite graphs.
• * Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and Alexander Schrijver for showing submodular minimization to be strongly polynomial.
• 2006:
• * Manindra Agrawal, Neeraj Kayal and Nitin Saxena, for the AKS primality test.
• * Mark Jerrum, Alistair Sinclair and Eric Vigoda, for approximating the permanent.
• * Neil Robertson and Paul Seymour, for the Robertson–Seymour theorem showing that graph minors form a well-quasi-ordering.
• 2009:
• * Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for the strong perfect graph theorem.
• * Daniel A. Spielman and Shang-Hua Teng, for smoothed analysis of linear programming algorithms.
• * Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture on the densest possible sphere packings.
• 2012:
• * Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving the approximation ratio for graph separators and related problems from to.
• * Anders Johansson, Jeff Kahn, and Van H. Vu for determining the threshold of edge density above which a random graph can be covered by disjoint copies of a given smaller graph.
• * László Lovász and Balázs Szegedy for characterizing subgraph multiplicity in sequences of dense graphs.
• 2015 :
• *Francisco Santos Leal for a counter-example of the Hirsch conjecture.
• 2018 :
• * Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Böttcher for The chromatic thresholds of graphs
• * Thomas Rothvoss for The Matching Polytope has Exponential Extension Complexity