The Fulkerson Prize for outstanding papers in the area of
discrete mathematics
Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...
is sponsored jointly by the
Mathematical Optimization Society (MOS) and the
American Mathematical Society
The American Mathematical Society (AMS) is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, and serves the national and international community through its publications, meetings, ...
(AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS 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.
Winners
* 1979:
**
Richard M. Karp for classifying many important
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
problems.
**
Kenneth Appel and
Wolfgang Haken for the
four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
.
**
Paul Seymour for generalizing the
max-flow min-cut theorem to
matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
s.
* 1982:
** D.B. Judin,
Arkadi Nemirovski,
Leonid Khachiyan,
Martin Grötschel,
László Lovász and
Alexander Schrijver for the
ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every ste ...
in
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
and
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
.
**
G. P. Egorychev and D. I. Falikman for proving
van der Waerden's conjecture that the matrix with all entries equal has the smallest
permanent of any
doubly stochastic matrix
In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
:\sum_i x_=\sum_j x_ ...
.
**
* 1985:
**
Jozsef Beck for tight bounds on the
discrepancy of
arithmetic progressions.
**
H. W. Lenstra Jr. for using the
geometry of numbers
Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice (group), lattice in \mathbb R^n, and the study of these lattices provides fundam ...
to solve
integer programs with few variables in time polynomial in the number of constraints.
**
Eugene M. Luks for a
polynomial time graph isomorphism algorithm for graphs of bounded
maximum degree.
* 1988:
**
Éva Tardos for finding
minimum cost circulations in
strongly polynomial time.
**
Narendra Karmarkar
Narendra Krishna Karmarkar (born 1956) is an Indian mathematician. He developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher.
He invented one of the first probably polynomial time algorithms for linear programming, w ...
for
Karmarkar's algorithm for
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
.
* 1991:
**
Martin E. Dyer,
Alan M. Frieze and
Ravindran Kannan for
random-walk-based
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s for the volume of convex bodies.
** Alfred Lehman for
0,1-matrix analogues of the theory of
perfect graphs.
** Nikolai E. Mnev for
Mnev's universality theorem, that every semialgebraic set is equivalent to the space of realizations of an
oriented matroid.
* 1994:
**
Louis Billera for finding bases of piecewise-polynomial function spaces over triangulations of space.
**
Gil Kalai for making progress on the
Hirsch conjecture by proving subexponential bounds on the diameter of ''d''-dimensional polytopes with ''n'' facets.
**
Neil Robertson,
Paul Seymour and
Robin Thomas for the six-color case of
Hadwiger's conjecture.
* 1997:
**
Jeong Han Kim for finding the
asymptotic growth rate of the
Ramsey numbers ''R''(3,''t'').
* 2000:
**
Michel X. Goemans and
David P. Williamson for
approximation algorithm
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s based on
semidefinite programming.
** Michele Conforti,
Gérard Cornuéjols, and
M. R. Rao for recognizing
balanced 0-1 matrices in
polynomial time.
* 2003:
**
J. F. Geelen, A. M. H. Gerards and A. Kapoor for the
GF(4) case of
Rota's conjecture on
matroid minors.
[2003 Fulkerson Prize citation](_blank)
retrieved 2012-08-18.
** Bertrand Guenin for a
forbidden minor characterization of the weakly bipartite graphs (graphs whose bipartite subgraph polytope is 0-1).
** Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and
Alexander Schrijver for showing
submodular minimization to be strongly polynomial.
* 2006:
**
Manindra Agrawal,
Neeraj Kayal and
Nitin Saxena, for the
AKS primality test.
[2006 Fulkerson Prize citation](_blank)
retrieved 2012-08-19.
**
Mark Jerrum,
Alistair Sinclair and Eric Vigoda, for
approximating the permanent.
**
Neil Robertson and
Paul Seymour, for the
Robertson–Seymour theorem showing that
graph minors form a
well-quasi-ordering.
* 2009:
**
Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for the
strong perfect graph theorem.
[2009 Fulkerson Prize citation](_blank)
retrieved 2012-08-19.
**
Daniel A. Spielman and
Shang-Hua Teng, for
smoothed analysis of
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
algorithms.
**
Thomas C. Hales and Samuel P. Ferguson, for proving the
Kepler conjecture on the densest possible
sphere packings.
* 2012:
**
Sanjeev Arora,
Satish Rao, and
Umesh Vazirani for improving the
approximation ratio
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
for
graph separators and related problems from
to
.
** Anders Johansson,
Jeff Kahn, and
Van H. Vu for determining the threshold of edge density above which a
random graph can be covered by disjoint copies of a given smaller graph.
**
László Lovász and
Balázs Szegedy for characterizing subgraph multiplicity in sequences of
dense graphs.
* 2015:
**
Francisco Santos Leal for ''a counter-example of the
Hirsch conjecture''.
* 2018:
**
Robert Morris,
Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and
Julia Böttcher for ''The chromatic thresholds of graphs''
**
Thomas Rothvoss for his work on the
extension complexity of the
matching polytope.
* 2021:
**
Béla Csaba,
Daniela Kühn,
Allan Lo,
Deryk Osthus, and
Andrew Treglown for ''Proof of the 1-factorization and Hamilton decomposition conjectures''
**
Jin-Yi Cai and
Xi Chen for ''Complexity of Counting CSP with Complex Weights''
**
Ken-Ichi Kawarabayashi and
Mikkel Thorup for ''Deterministic Edge Connectivity in Near-Linear Time''
Source: Mathematical Optimization Society official website.
* 2024:
** Ben Cousins and
Santosh Vempala for ''Gaussian cooling and
algorithms for volume and Gaussian volume''
** Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao for ''Equiangular lines with a fixed angle''
** Nathan Keller and Noam Lifshitz for ''The junta method for hypergraphs and the Erdős–Chvátal simplex conjecture''
Source: American Mathematical Society official website.
See also
*
List of mathematics awards
References
{{reflist, colwidth=30em
External links
Official web page(MOS)
(AMS website)
AMS archive of past prize winners
Computer science awards
Awards of the American Mathematical Society
Awards of the Mathematical Optimization Society
Triennial events
1979 establishments in the United States
Discrete mathematics
Awards established in 1979