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 continu ...
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

Source
Mathematical Optimization Society
* 1979: ** Richard M. Karp for classifying many important
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
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 sh ...
. ** Paul Seymour for generalizing the max-flow min-cut theorem to
matroid In combinatorics, a branch of mathematics, 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 axiomatically, the most significant being ...
s. * 1982: ** D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grötschel, László Lovász and
Alexander Schrijver Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in Ams ...
for the ellipsoid method 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 are represented by linear relationships. Linear programming is ...
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 combi ...
. ** 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 Discrepancy may refer to: Mathematics * Discrepancy of a sequence * Discrepancy theory in structural modelling * Discrepancy of hypergraphs, an area of discrepancy theory * Discrepancy (algebraic geometry) Statistics * Discrepancy function in th ...
of arithmetic progressions. ** H. W. Lenstra Jr. for using the geometry of numbers to solve
integer program An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective ...
s with few variables in time polynomial in the number of constraints. **
Eugene M. Luks Eugene Michael Luks (born circa 1940) is an American mathematician and computer scientist, a professor emeritus of computer and information science at the University of Oregon. He is known for his research on the graph isomorphism problem and o ...
for a
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
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 Circa 1956) is an Indian Mathematician. Karmarkar developed Karmarkar's algorithm. He is listed as an ISI highly cited researcher. He invented one of the first provably polynomial time algorithms for linear pro ...
for
Karmarkar's algorithm Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also po ...
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 are represented by linear relationships. Linear programming is ...
. * 1991: ** Martin E. Dyer,
Alan M. Frieze Alan M. Frieze (born 25 October 1945 in London, England) is a professor in the Department of Mathematical Sciences at Carnegie Mellon University, Pittsburgh, United States. He graduated from the University of Oxford in 1966, and obtained his PhD f ...
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 solu ...
s for the volume of convex bodies. ** Alfred Lehman for 0,1-matrix analogues of the theory of
perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph ( clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is per ...
s. ** 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 In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an ''n''-facet polytope in ''d''-dimensional Euclidean space has diameter no more than ''n'' − ''d''. That is ...
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 Jeong Han Kim (; born July 20, 1962) is a South Korean mathematician. He studied physics and mathematical physics at Yonsei University, and earned his Ph.D. in mathematics at Rutgers University. He was a researcher at AT&T Bell Labs and at Micr ...
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 solu ...
s based on semidefinite programming. ** Michele Conforti, Gérard Cornuéjols, and M. R. Rao for recognizing balanced 0-1 matrices in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. * 2003: ** J. F. Geelen, A. M. H. Gerards and A. Kapoor for the GF(4) case of Rota's conjecture on
matroid minor In the mathematical theory of matroids, a minor of a matroid ''M'' is another matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restricti ...
s.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 Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in Ams ...
for showing submodular minimization to be strongly polynomial. * 2006: ** Manindra Agrawal, Neeraj Kayal and
Nitin Saxena Nitin Saxena (born 3 May 1981Saxena's CV at University of Bonn
) is ...
, for the AKS primality test.2006 Fulkerson Prize citation
retrieved 2012-08-19.
** Mark Jerrum,
Alistair Sinclair :' Alistair Sinclair (born 1960) is a British computer scientist and computational theorist. Sinclair received his B.A. in mathematics from St. John’s College, Cambridge in 1979, and his Ph.D. in computer science from the University of Edinbu ...
and Eric Vigoda, for approximating the permanent. ** Neil Robertson and Paul Seymour, for the
Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that i ...
showing that
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only i ...
s 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 Shang-Hua Teng (; born 1964) is a Chinese-American computer scientist. He is the Seeley G. Mudd Professor of Computer Science and Mathematics at the University of Southern California. Previously, he was the chairman of the Computer Science Depart ...
, for
smoothed analysis In theoretical computer science, smoothed analysis is a way of measuring the complexity of an algorithm. Since its introduction in 2001, smoothed analysis has been used as a basis for considerable research, for problems ranging from mathematica ...
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 are represented by linear relationships. Linear programming is ...
algorithms. ** Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture on the densest possible
sphere packing In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three- dimensional Euclidean space. However, sphere pack ...
s. * 2012: **
Sanjeev Arora Sanjeev Arora (born January 1968) is an Indian American theoretical computer scientist. Life He was a visiting scholar at the Institute for Advanced Study in 2002–03. In 2008 he was inducted as a Fellow of the Association for Computing Mac ...
, Satish Rao, and Umesh Vazirani for improving the
approximation ratio An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix '' ...
for graph separators and related problems from O(\log n) to O(\sqrt). ** Anders Johansson, Jeff Kahn, and
Van H. Vu Van H. Vu ( vi, Vũ Hà Văn) is a Vietnamese mathematician, Percey F. Smith Professor of Mathematics at Yale University.CV
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 Francisco (Paco) Santos Leal (born May 28, 1968) is a Spanish mathematician at the University of Cantabria, known for finding a counterexample to the Hirsch conjecture in polyhedral combinatorics. In 2015 he won the Fulkerson Prize for this resear ...
for ''a counter-example of the
Hirsch conjecture In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an ''n''-facet polytope in ''d''-dimensional Euclidean space has diameter no more than ''n'' − ''d''. That is ...
''. * 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 In convex geometry and polyhedral combinatorics, the extension complexity is a convex polytope P is the smallest number of facets among convex polytopes Q that have P as a projection. In this context, Q is called an extended formulation of P; it m ...
of the
matching polytope In graph theory, the matching polytope of a given graph is a geometric object representing the possible matchings in the graph. It is a convex polytope each of whose corners corresponds to a matching. It has great theoretical importance in the the ...
. * 2021: **
Béla Csaba Béla may refer to: * Béla (crater), an elongated lunar crater * Béla (given name), a common Hungarian male given name See also * Bela (disambiguation) * Belá (disambiguation) * Bělá (disambiguation) Bělá, derived from ''bílá'' (''wh ...
,
Daniela Kühn Daniela Kühn (born 1973) is a German mathematician and the Mason Professor in Mathematics at the University of Birmingham in Birmingham, England.
, Allan Lo, Deryk Osthus, and
Andrew Treglown Andrew is the English form of a given name common in many countries. In the 1990s, it was among the top ten most popular names given to boys in English-speaking countries. "Andrew" is frequently shortened to "Andy" or "Drew". The word is derive ...
for ''Proof of the 1-factorization and Hamilton decomposition conjectures'' **
Jin-Yi Cai Jin-Yi Cai (Chinese: 蔡进一; born 1961) is a Chinese American mathematician and computer scientist. He is a professor of computer science, and also thSteenbock Professor of Mathematical Sciencesat the University of Wisconsin–Madison. His rese ...
and Xi Chen for ''Complexity of Counting CSP with Complex Weights'' **
Ken-Ichi Kawarabayashi Ken-ichi Kawarabayashi ( ja, 河原林 健一, born 1975) is a Japanese graph theorist who works as a professor at the National Institute of Informatics and is known for his research on graph theory (particularly the theory of graph minors) and gr ...
and
Mikkel Thorup Mikkel Thorup (born 1965) is a Danish computer scientist working at University of Copenhagen. He completed his undergraduate education at Technical University of Denmark and his doctoral studies at Oxford University in 1993. From 1993 to 199 ...
for ''Deterministic Edge Connectivity in Near-Linear Time''


See also

*
List of mathematics awards This list of mathematics awards is an index to articles about notable awards for mathematics. The list is organized by the region and country of the organization that sponsors the award, but awards may be open to mathematicians from around the wo ...


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 Triennial events 1979 establishments in the United States