
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, wellreferenced 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.
Guidelines
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, wellreferenced 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.
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.

Graham, Klee, 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.

Graham, Karp, 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.

Hoffman, Karp, 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.

Groetschel, Padberg, 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.

Billera, Groetschel, 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.

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

Kannan, Graham, 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.

Williamson, Cornuejols, Odlyzko 
2006 
Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES
is in P", Annals of Mathematics, Volume 160, issue 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, Volume 51, Issue 4, 2004, Pages 671697.
Neil Robertson and Paul D. Seymour, "Graph Minors XX. Wagner's conjecture",
Journal of Combinatorial Theory, Series B, Volume 92, Issue 2 , 2004, Pages 325357.

Goemans, Alon, Cunningham 
top
of page 
