The Fulkerson Prize
citations 2012
past winners
The Fulkerson Prize for outstanding papers in the area of discrete
mathematics is sponsored jointly by the Mathematical Optimization Society and the American
Mathematical Society. Beginning in 1979, up to three awards of $750 each will be presented at
each (triennial) International Symposium on Mathematical Programming; they will be 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. Beginning in 1994, the amount of each award is $1,500.
Guidelines
To be eligible, a paper should be the final publication of the main result(s) and should
have been published in a recognized journal, or in a comparable, wellrefereed volume intended
to publish final publications only, during the six calendar years preceding the year of the
International Symposium on Mathematical Programming. The publication year for the paper will
be defined to be the print publication year, for any volume that appears in print, or the
electronic publication year, for any volume that appears only in electronic form. 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 optimization, applied combinatorics, and related subjects. While research work in
these areas is usually not far removed from practical applications, the judging of papers will
be based on their mathematical quality and significance.
The Prize Committee
The Prize Committee for the
awards will have two members appointed by the Chair of the MOS 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. One of
the initial Mathematical Optimization Society appointees will be the first chair of the
committee; subsequent chairs will be chosen by the Prize Committee from among its members and
should whenever possible be veterans of the previous round of awards. The Prize 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
mathematicians.
top of page
Past Winners of the Fulkerson Prize
Year 
Winners 
Selection Committee 
1979 
Kenneth Appel and Wolfgang Haken, "Every planar map is fourcolorable,
Part I: Discharging", Illinois J. Math 21 (1977), 429490.
Richard M. Karp, "On the computational complexity of combinatorial
problems", Networks 5 (1975), 4568.
Paul D. Seymour, "The matroids with the maxflow mincut
property", Journal of Combinatorial Theory B 23 (1977), 189222.

R. Graham,
V. Klee,
A. Tucker

1982 
Shared one prize:
L.G. Khachiyan, "A polynomial algorithm in linear programming",
Doklady Akademiia Nauk SSR 244 (1979), 10931096
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), 357369.
Shared one prize:
G.P. Egorychev, "The solution of van der Waerden's problem for
permanents", Dokl. Akad. Sci. SSSR 258 (1981) 10411044
and
D.I. Falikman, "A proof of the van der Waerden conjecture on the permanent
of a double stochastic matrix", Mat. Zametiki 29 (1981), 931938.
Martin Grötschel, Laszlo Lovasz, and Alexander Schrijver, "The
ellipsoid method and its consequences in combinatorial optimization", Combinatorica 1
(1981), 169197.

R. Graham,
R. Karp,
V. Klee

1985 
Jozsef Beck, "Roth's estimate of the discrepancy of
integer sequences is nearly sharp", Combinatorica 1 (1981), 319325.
H.W. Lenstra, Jr., "Integer programming with a fixed number of
variables", Mathematics of Operations Research 8 (1983), 538548.
Eugene M. Luks, "Isomorphism of graphs of bounded valence can be tested
in polynomial time", Journal of Computer and System Sciences 25 (1982), 4265.

A. Hoffman,
R. Karp,
L. Lovasz

1988 
Eva Tardos, "A strongly polynomial minimum cost
circulation algorithm", Combinatorica 5 (1985), 247256.
Narendra Karmarkar, "A new polynomialtime algorithm for linear
programming", Combinatorica 4 (1984), 373395.

M. Grötschel,
M. Padberg,
G. Rota

1991 
Alfred Lehman, "The widthlength 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,
101105.
Nikolai E. Mnev, "The universality theorems on the classification
problem of configuration varieties and convex polytope varieties" in: O. Ya. Viro (ed.),
Topology and GeometryRohlin Seminar, Lecture Notes in Mathematics 1346, SpringerVerlag,
Berlin, 1988, 527544.
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), 117.

L. Billera,
M. Grötschel,
P. Seymour

1994 
Lou Billera, "Homology of smooth splines: generic triangulations and a
conjecture of Strang", Transactions of the American Mathematical Society 310 (1988),
325340.
Neil Robertson, Paul D. Seymour, and Robin Thomas, "Hadwiger's
conjecture for K6free graphs", Combinatorica 13 (1993), 279361.
Gil Kalai, "Upper bounds for the diameter and height of graphs of
convex polyhedra", Discrete and Computational Geometry 8 (1992), 363372.

A. Schrijver,
A. Hoffman,
E. Tardos

1997 
Jeong Han Kim, "The Ramsey Number R(3,t) has order of magnitude t^2/log
t", Random Structures and Algorithms 7 (1995), 173207.

R. Graham,
R. Kannan,
E. Tardos

2000 
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), 11151145.
Michele Conforti, Gerard Cornuejols, M. R. Rao, "Decomposition of
balanced matrices", Journal of Combinatorial Theory B 77 (1999), 292406.

R. Kannan,
R. Graham,
W. Cook 
2003 
J. F. Geelen, A. M. H. Gerards, A. Kapoor,
"The Excluded Minors for GF(4)Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247299.
B. Guenin,
"A characterization of weakly bipartite graphs",
Journal of Combinatorial Theory B 83 (2001) 112168.
Shared one prize:
S. Iwata, L. Fleischer, and S. Fujishige,
"A combinatorial, strongly polynomialtime algorithm for minimizing submodular functions",
Journal of the ACM 48 (2001), 761777
and
A. Schrijver,
"A combinatorial algorithm minimizing submodular functions in strongly polynomial time",
Journal of Combinatorial Theory B 80 (2000), 346355.

D. Williamson,
G. Cornuejols,
A. Odlyzko

2006 
Manindra Agrawal, Neeraj Kayal
and Nitin Saxena, "PRIMES is in P", Annals of Mathematics 160,
No. 2 (2004), Pages 781793.
Mark Jerrum, Alistair Sinclair
and Eric Vigoda, "A polynomialtime approximation algorithm for the permanent
of a matrix with nonnegative entries", J. ACM 51, No. 4 (2004), Pages
671697.
Neil Robertson and Paul
D. Seymour, "Graph Minors XX. Wagner's conjecture", Journal of
Combinatorial Theory Series B 92, No 2, (2004), Pages 325357.

M. Goemans,
N. Alon,
W. Cunningham 
2009 
Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas,
"The strong perfect graph theorem", Annals of Mathematics 164 (2006) 51229.
Shared one prize:
Thomas C. Hales,
"A proof of the Kepler conjecture", Annals of Mathematics 162 (2005) 10631183.
Samuel P. Ferguson,
"Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36 (2006) 167204.
Daniel Spielman and
ShangHua Teng, "Smoothed analysis of algorithms: Why the simplex
algorithm usually takes polynomial time", Journal of the ACM 51 (2004)
385463.

W. Cook,
M. Goemans,
D. Kleitman 
2012 
Sanjeev Arora, Satish Rao, and Umesh Vazirani,
"Expander flows, geometric embeddings and graph partitioning", J. ACM, 56 (2009), 137.
Anders Johansson, Jeff Kahn, and Van Vu,
"Factors in random graphs", Random Structures and Algorithms 33 (2008), 128.
Lászlo Lovász and Balázs Szegedy,
"Limits of dense graph sequences", Journal of Combinatorial Theory Series B 96 (2006), 933957.

K. Aardal
Paul Seymour
Richard Stanley

