Home | Contact | About MOS | Membership | Publications | Prizes | Meetings | IPCO | ISMP | Links | Album | Jobs
Mathematical Optimization Society

MOS Prizes

MOS Prizes

 

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