|
The Fulkerson Prize
citations 2021
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, well-refereed 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 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.
|
R. Graham,
V. Klee,
A. Tucker
|
| 1982 |
Shared one prize:
Leonid G. Khachiyan, "A polynomial algorithm in linear programming",
Doklady Akademiia Nauk SSR 244 (1979), 1093-1096
and
David B. Iudin and Arkadi 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, Lászlo Lovás, and Alexander Schrijver, "The
ellipsoid method and its consequences in combinatorial optimization", Combinatorica 1
(1981), 169-197.
|
R. Graham,
R. Karp,
V. Klee
|
| 1985 |
Jozsef Beck, "Roth's estimate of the discrepancy of
integer sequences is nearly sharp", Combinatorica 1 (1981), 319-325.
Hendrik 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.
|
A. Hoffman,
R. Karp,
L. Lovasz
|
| 1988 |
Éva 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.
|
M. Grötschel,
M. Padberg,
G. Rota
|
| 1991 |
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.
|
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),
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.
|
A. Schrijver,
A. Hoffman,
É. 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), 173-207.
|
R. Graham,
R. Kannan,
É. 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), 1115-1145.
Michele Conforti, Gérard Cornuéljols, M. R. Rao, "Decomposition of
balanced matrices", Journal of Combinatorial Theory B 77 (1999), 292-406.
|
R. Kannan,
R. Graham,
W. Cook |
| 2003 |
Jim F. Geelen, A. M. H. Gerards, Ajai Kapoor,
"The Excluded Minors for GF(4)-Representable Matroids", Journal of Combinatorial Theory B 79 (2000), 247-299.
Bertrand Guenin,
"A characterization of weakly bipartite graphs",
Journal of Combinatorial Theory B 83 (2001) 112-168.
Shared one prize:
Satoru Iwata, Lisa Fleischer, and Satoru Fujishige,
"A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions",
Journal of the ACM 48 (2001), 761-777
and
Alexander Schrijver,
"A combinatorial algorithm minimizing submodular functions in strongly polynomial time",
Journal of Combinatorial Theory B 80 (2000), 346-355.
|
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 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 51, No. 4 (2004), Pages
671-697.
Neil Robertson and Paul
D. Seymour, "Graph Minors XX. Wagner's conjecture", Journal of
Combinatorial Theory Series B 92, No 2, (2004), Pages 325-357.
|
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) 51-229.
Shared one prize:
Thomas C. Hales,
"A proof of the Kepler conjecture", Annals of Mathematics 162 (2005) 1063-1183.
Samuel P. Ferguson,
"Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36 (2006) 167-204.
Daniel Spielman and
Shang-Hua Teng, "Smoothed analysis of algorithms: Why the simplex
algorithm usually takes polynomial time", Journal of the ACM 51 (2004)
385-463.
|
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), 1-37.
Anders Johansson, Jeff Kahn, and Van Vu,
"Factors in random graphs", Random Structures and Algorithms 33 (2008), 1-28.
Lászlo Lovász and Balázs Szegedy,
"Limits of dense graph sequences", Journal of Combinatorial Theory Series B 96 (2006), 933-957.
|
K. Aardal
P. Seymour
R. Stanley
|
| 2015 |
Francisco Santos,
"A Counterexample to the Hirsch Conjecture", Annals of Mathematics, 2012
|
M. Conforti
F. Eisenbrand
E. Schulte
|
| 2018 |
Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert Morris,
"The chromatic thresholds of graphs", Adv. Math. 235, 261-295 (2013)
Thomas Rothvoß,
" The Matching Polytope has Exponential Extension Complexity.", J. ACM 64(6): 41:1-41:19 (2017)
|
M. Chudnovsky
F. Eisenbrand
M. Grötschel
|
| 2021 |
Béla Csaba, Daniela Kühn, Allan Lo, Deryk Osthus and Andrew Treglown,
"Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, vol. 244, no. 1154, 2016.
Jin-Yi Cai and Xi Chen,
"Complexity of Counting CSP with Complex Weights", Journal of the ACM, vol. 64, no. 3, 2017.
Ken-Ichi Kawarabayashi and Mikkel Thorup,
"Deterministic Edge Connectivity in Near-Linear Time", Journal of the ACM, vol. 66, no. 1, 2018.
|
Gérard Cornuéjols
Éva Czabarka
Dan Spielman
|
|
