2009 Fulkerson Prize Citation

Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas
"The strong perfect graph theorem", Annals of Mathematics 164 (2006) 51-229.

Claude Berge introduced the class of perfect graphs in 1960 together with a possible characterization in terms of forbidden subgraphs. The resolution of Berge's strong perfect graph conjecture quickly became one of the most sought after goals in graph theory. The pursuit of the conjecture brought together four important elements: vertex colorings, stable sets, cliques, and clique covers. Moreover, D. R. Fulkerson established connections between perfect graphs and integer programming through his theory of anti-blocking polyhedra. A graph is called perfect if for every induced subgraph H the clique-covering number of H is equal to the cardinality of its largest stable set. The strong perfect graph conjecture states that a graph is perfect if and only if neither it nor its complement contains as an induced subgraph an odd circuit having at least five edges. The elegance and simplicity of this possible characterization led to a great body of work in the literature, culminating in the Chudnovsky et al. proof, announced in May 2002, just one month before Berge passed away. The long, difficult, and creative proof by Chudnovsky et al. is one of the great achievements in discrete mathematics.

Thomas C. Hales,
"A proof of the Kepler conjecture", Annals of Mathematics 162 (2005) 1063-1183.
Samuel P. Ferguson
"Sphere Packings, V. Pentahedral Prisms", Discrete and Computational Geometry 36 (2006) 167-204.

In 1611 Johannes Kepler asserted that the densest packing of equal-radius spheres is obtained by the familiar cannonball arrangement. This statement is known as the Kepler conjecture and it is a component of Hilbert's 18th problem. After four centuries, Ferguson and Hales have now proven Kepler's assertion. The Ferguson-Hales proof develops deep connections between sphere packings and mathematical programming, making heavy use of linear programming duality and branch and bound to establish results on the density of candidate configurations of spheres. The beautiful geometric arguments and innovative use of computational tools make this a landmark result in both geometry and discrete mathematics.

Daniel A. Spielman and Shang-Hua Teng
"Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", Journal of the ACM 51 (2004) 385-463.

George Dantzig's simplex algorithm for linear programming is a fundamental tool in applied mathematics. The work of Spielman and Teng is an important step towards providing a theoretical understanding of the algorithm's great success in practice despite its known exponential worst-case behavior. The smoothed analysis introduced by the authors fits nicely between overly pessimistic worst-case results and the average-case theory developed in the 1980s. In smoothed analysis, the performance of an algorithm is measured under small perturbations of arbitrary real inputs. The Spielman-Teng proof that the simplex algorithm runs in polynomial-time under this measure combines beautiful technical results that intersect multiple areas of discrete mathematics. Moreover, the general smoothed analysis framework is one that can be applied in many algorithmic settings and it is now established as an important technique in theoretical computer science.