The Fulkerson Prize

call for nominations 2009
citations 2006
past winners

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society. Up to three awards of $1500 each are presented at each (triennial) International Symposium of the Mathematical Programming Society. Originally, the prizes were paid out of a memorial fund administered by the American Mathematical Society that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

Papers to be eligible should form the final publication of the main result(s) and should have been published in a recognized journal, or in a comparable, well-referenced volume intended to publish final publications only, during the six calendar years preceding the year of the Symposium. Extended abstracts and prepublications, and articles published in journals, journal sections or proceedings that are intended to publish nonfinal papers, are not included. The extended period of six years is in recognition of the fact that the value of fundamental work cannot always be immediately assessed. The prizes will be given for single papers, not series of papers or books, and in the event of joint authorship the prize will be divided.

The term 'discrete mathematics' is intended to include graph theory, networks, mathematical programming, applied combinatorics, and related subjects. While research work in these areas is usually not far removed practical applications, the judging of papers will be based on their mathematical quality and significance.

The Selection Committee for the awards will have two members appointed by the Chair of MPS and one member appointed by the President of the American Mathematical Society. The committee members will serve for at most two rounds of awards, with terms overlapping where possible for the sake of continuity. Chairs should whenever possible be veterans of the previous round of awards. The Selection Committee will devise its own procedures for acquiring nominations or otherwise searching out papers of interest, taking pains, however, not to overlook the work of young, relatively unknown mathematicicans.

Kenneth Appel and Wolfgang Haken, "Every planar map is four-colorable, Part I: Discharging", Illinois J. Math 21 (1977), 429-490.

Richard M. Karp, "On the computational complexity of combinatorial problems", Networks 5 (1975), 45-68.

Paul D. Seymour, "The matroids with the max-flow min-cut property", Journal of Combinatorial Theory B 23 (1977), 189-222.

Shared one prize:
L.G. Khachiyan, "A polynomial algorithm in linear programming", Doklady Akademiia Nauk SSR 244 (1979), 1093-1096
and
D.B. Iudin and A.S. Nemirovskii, "Informational complexity and effective methods of solution for convex extremal problems", Ekonomika i Matematicheski Metody 12 (1976), 357-369.

Shared one prize:
G.P. Egorychev, "The solution of van der Waerden's problem for permanents", Dokl. Akad. Sci. SSSR 258 (1981) 1041-1044
and
D.I. Falikman, "A proof of the van der Waerden conjecture on the permanent of a double stochastic matrix", Mat. Zametiki 29 (1981), 931-938.

Martin Grötschel, Laszlo Lovasz, and Alexander Schrijver, "The ellipsoid method and its consequences in combinatorial optimization", Combinatorica 1 (1981), 169-197.

Jozsef Beck, "Roth's estimate of the discrepancy of integer sequences is nearly sharp", Combinatorica 1 (1981), 319-325.

H.W. Lenstra, Jr., "Integer programming with a fixed number of variables", Mathematics of Operations Research 8 (1983), 538-548.

Eugene M. Luks, "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences 25 (1982), 42-65.

Eva Tardos, "A strongly polynomial minimum cost circulation algorithm", Combinatorica 5 (1985), 247-256.

Narendra Karmarkar, "A new polynomial-time algorithm for linear programming", Combinatorica 4 (1984), 373-395.

Alfred Lehman, "The width-length inequality and degenerate projective planes", in W. Cook and P.D. Seymour (eds.), "Polyhedral Combinatorics", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, 1990, AMS, 101-105.

Nikolai E. Mnev, "The universality theorems on the classification problem of configuration varieties and convex polytope varieties" in: O. Ya. Viro (ed.), Topology and Geometry-Rohlin Seminar, Lecture Notes in Mathematics 1346, Springer-Verlag, Berlin, 1988, 527-544.

Martin Dyer, Alan Frieze, and Ravi Kannan, "A random polynomial time algorithm for approximating the volume of convex bodies", Journal of the ACM 38 (1991), 1-17.

Lou Billera, "Homology of smooth splines: generic triangulations and a conjecture of Strang", Transactions of the American Mathematical Society 310 (1988), 325-340.

Neil Robertson, Paul D. Seymour, and Robin Thomas, "Hadwiger's conjecture for K6-free graphs", Combinatorica 13 (1993), 279-361.

Gil Kalai, "Upper bounds for the diameter and height of graphs of convex polyhedra", Discrete and Computational Geometry 8 (1992), 363-372.

Michel X. Goemans and David P. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM 42 (1995), 1115-1145.

Michele Conforti, Gerard Cornuejols, M. R. Rao, "Decomposition of balanced matrices", Journal of Combinatorial Theory B 77 (1999), 292-406.

J. F. Geelen, A. M. H. Gerards, A. Kapoor, "The Excluded Minors for GF(4)-Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247-299.

B. Guenin, "A characterization of weakly bipartite graphs", Journal of Combinatorial Theory B 83 (2001) 112-168.

Shared one prize:
S. Iwata, L. Fleischer, and S. Fujishige, "A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions", Journal of the ACM 48 (2001), 761-777
and
A. Schrijver, "A combinatorial algorithm minimizing submodular functions in strongly polynomial time", Journal of Combinatorial Theory B 80 (2000), 346-355.

Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics, Volume 160, issue 2, 2004, Pages 781--793.

Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", J. ACM, Volume 51, Issue 4, 2004, Pages 671--697.

Neil Robertson and Paul D. Seymour, "Graph Minors XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, Volume 92, Issue 2 , 2004, Pages 325--357.