HOME

TheInfoList



OR:

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
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
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
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 O(\log n) to O(\sqrt). ** 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 O^*(n^3) 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