The original version of this story appeared in Quanta Magazine.

George Dantzig’s Unlikely Discovery

In 1939, George Dantzig, a first-year graduate student at UC Berkeley, arrived late to his statistics class and copied two statistical problems from the blackboard, assuming they were homework. He later recalled these problems were "unusually challenging," but upon solving them, he discovered they were famous unsolved problems in statistics. This serendipitous breakthrough would form the basis of his doctoral dissertation and later inspire the film Good Will Hunting.

The Birth of the Simplex Method

Dantzig earned his doctorate in 1946, shortly after World War II. With the war’s global scale and resource constraints, the U.S. Air Force sought methods to optimize resource allocation across thousands of variables. Dantzig, tasked with solving such complex optimization problems, invented the simplex method—a geometric algorithm that transforms linear constraints into a polyhedral search space, aiming to find the optimal solution by traversing vertices of this shape.

Nearly 80 years later, the simplex method remains a cornerstone of logistics and supply-chain decision-making, renowned for its efficiency. As Sophie Huiberts of France’s National Center for Scientific Research (CNRS) noted, "It has always executed quickly, and no inefficiency has been observed in practice."

The Theoretical Paradox

Despite its practical success, a critical theoretical issue emerged: in 1972, mathematicians proved the simplex method’s runtime could grow exponentially with the number of constraints. This raised doubts about its worst-case reliability. Huiberts explained, "Traditional algorithmic analysis tools cannot characterize the simplex method’s behavior in the worst case."

A Breakthrough in Complexity Theory

In a December 2024 paper to be presented at the Foundations of Computer Science conference, Huiberts and Eleon Bach (a doctoral student at the Technical University of Munich) resolved this paradox. Building on Daniel Spielman and Shang-Hua Teng’s 2001 work, they introduced controlled randomness to the simplex method, reducing runtime to polynomial time (e.g., (O(n^2))) with significantly smaller exponents. Teng praised their work as "brilliant and elegant," while László Végh (University of Bonn) called it "impressive technical progress" integrating prior insights with novel innovations.

The Simplex Method as Geometric Optimization

The simplex method models linear programming problems as geometric searches. For example, maximizing profit from armoires ((a)), beds ((b)), and chairs ((c)) with constraints (a + b + c \leq 50), (a \leq 20), and (c \leq 24) translates to finding the vertex of a 3D polyhedron (defined by the constraints) that maximizes (3a + 2b + c).

Without a global map, traversing the polyhedron’s vertices can lead to inefficiency. Spielman and Teng’s 2001 result showed random perturbations (e.g., probabilistic edge choices) prevent exponential growth, but their bound had a large exponent ((n^{30})). Huiberts and Bach’s new analysis reduces this to a more manageable form, proving the simplex method’s runtime is bounded by a fixed polynomial in (n).

Implications for the Future

The work confirms the simplex method’s practical efficiency is theoretically justified, though achieving linear-time scaling remains an open challenge. "The North Star is to reduce runtime to (O(n))," Huiberts noted, "but this requires entirely new strategies."

Julian Hall (University of Edinburgh), who develops linear programming software, stated, "This work provides mathematical confidence that real-world problems solved by the simplex method will always run in polynomial time, easing fears of exponential complexity."

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.