• 1979: •
Richard M. Karp for classifying many important
NP-complete problems. •
Kenneth Appel and
Wolfgang Haken for the
four color theorem. •
Paul Seymour for generalizing the
max-flow min-cut theorem to
matroids. • 1982: • D.B. Judin,
Arkadi Nemirovski,
Leonid Khachiyan,
Martin Grötschel,
László Lovász and
Alexander Schrijver for the
ellipsoid method in
linear programming and
combinatorial optimization. •
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. • • 1985: •
Jozsef Beck for tight bounds on the
discrepancy of
arithmetic progressions. •
H. W. Lenstra Jr. for using the
geometry of numbers 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 for
Karmarkar's algorithm for
linear programming. • 1991: •
Martin E. Dyer,
Alan M. Frieze and
Ravindran Kannan for
random-walk-based
approximation algorithms 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 algorithms 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. • Bertrand Guenin for a
forbidden minor characterization of the weakly bipartite graphs (graphs whose bipartite subgraph polytope is 0-1). •
Mark Jerrum,
Alistair Sinclair and Eric Vigoda, for
approximating the permanent. •
Daniel A. Spielman and
Shang-Hua Teng, for
smoothed analysis of
linear programming algorithms. • 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. • 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==