Linear programming (LP) is one of the pillars of mathematical optimization. We have known since the late 20th century that LPs can be solved in polynomial time. However, standard algorithms—such as the ellipsoid method and continuous interior-point methods (IPMs)—are only weakly polynomial. This means their running times depend not just on the structural dimensions of the problem (the number of variables $n$ and constraints $m$), but also on the bit-length $L$ of the input numbers. If an LP contains massive coefficients or requires extreme numerical precision, these algorithms slow down, even if the underlying geometry remains identical.
A long-standing open question in computer science is whether general linear programming can be solved in strongly polynomial time. A strongly polynomial algorithm's iteration count would be bounded strictly by a polynomial in $n$ and $m$, and its arithmetic operations would remain independent of the magnitude of the input data.
Recent research has approached this challenge from two sides: proving fundamental limits on why traditional continuous and combinatorial methods fail to be strongly polynomial, and developing new geometric, scaling-invariant frameworks that bring us closer to this goal.
The Geometric Barriers of Continuous Solvers
Interior-point methods solve LPs by tracing a smooth, continuous trajectory known as the central path through the interior of the feasible region. For decades, researchers wondered if the number of steps required to follow this path could be bounded purely by the problem's dimensions. Recent work has definitively answered this in the negative by showing that the central path can be deformed adversarially.
Xavier Allamigeon et al. provided a major breakthrough in Log-Barrier Interior Point Methods Are Not Strongly Polynomial by constructing a specific family of linear programs where standard log-barrier IPMs are forced to take an exponential number of iterations. The authors extended this impossibility result to all path-following methods in No self-concordant barrier interior point method is strongly polynomial, proving that no self-concordant barrier function can guarantee a strongly polynomial runtime.
The intuition behind this failure lies in how the central path behaves when confronted with highly asymmetric or poorly scaled constraints. As demonstrated by Manru Zong et al. in Short-step methods are not strongly polynomial-time, one can construct "ill-behaved" central paths that twist excessively through narrow geometric corridors. To stay close to such a path, "short-step" methods are forced to take miniscule steps, causing the total iteration count to grow unboundedly with the problem size, independent of precision.
Weakly Polynomial IPM:
[Start] --> (Twisting Central Path influenced by bit-length L) --> [Tiny Steps] --> [Optimal]
Strongly Polynomial Ideal:
[Start] ---------------------> (Direct Geometric Route) ---------------------> [Optimal]
The Combinatorial Limits of Edge-Following
If continuous paths through the interior are vulnerable to geometric twisting, what about discrete paths along the boundary? The classic Simplex method navigates along the edges of the LP polyhedron, moving from vertex to vertex. Its efficiency depends entirely on the pivot rule used to select the next edge.
While the Simplex method is highly efficient in practice, finding a pivot rule that guarantees a polynomial path length in the worst case remains an open problem. Georg Loho et al. exposed the limits of a broad class of selection strategies in Lower bounds for ranking-based pivot rules. The authors proved superpolynomial and subexponential lower bounds for "ranking-based" rules—those that make decisions based on the relative order of objective gains rather than raw numerical values. This indicates that simply combining standard criteria like index order and reduced costs cannot bypass worst-case complexity barriers.
This combinatorial bottleneck is deeply tied to the underlying geometry of polyhedra. As Moise Blanchard et al. detailed in On the Length of Monotone Paths in Polyhedra, the existence of exponentially long monotone paths in certain worst-case polytopes makes it incredibly difficult to design a universal, blind pivot rule that always finds a short path to the optimum.
Exploiting Special Structures
While a strongly polynomial algorithm for general LPs remains elusive, researchers have successfully designed them for specialized problem classes by exploiting unique combinatorial structures:
- Totally Unimodular LPs: When every square submatrix of the constraint matrix has a determinant of $0, 1,$ or $-1$, the problem simplifies significantly. Tobias Brunsch et al. proved in Solving Totally Unimodular LPs with the Shadow Vertex Algorithm that a classic simplex pivoting rule—the Shadow Vertex algorithm—can solve this broad class in strongly polynomial time.
- Lattice Polytopes: For LPs defined over integer lattices, Alberto Del Pia et al. developed algorithms in Short Simplex Paths in Lattice Polytopes that guarantee short, polynomially bounded paths from any starting vertex to the optimal solution.
- Game Theory Connections: In Combinatorial Simplex Algorithms Can Solve Mean Payoff Games, Xavier Allamigeon et al. utilized a tropical geometry implementation of the simplex method to show that if a strongly polynomial pivot rule exists, it would immediately unlock strongly polynomial solutions for mean payoff games.
Scaling Invariance and Circuit Geometry
To bridge the gap between these structured successes and general linear programming, recent work has focused on scaling-invariant algorithms. The core idea is to decouple the algorithm's performance from how the problem is numerically presented, making its runtime depend strictly on the intrinsic geometry of the constraint matrix $A$.
Daniel Dadush et al. introduced a major advancement in A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix (with its full journal version in A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix). The authors designed an interior-point method that utilizes a novel "circuit ratio digraph" and a refined potential function. This framework bounds the iteration complexity by $O(n^{2.5} \log n)$ multiplied by a geometric condition number of the matrix $A$, completely eliminating dependence on the objective or right-hand side vectors.
This geometric perspective relies heavily on the concept of circuits—the minimal linearly dependent subsets of the columns of the constraint matrix. By analyzing how these circuits interact, Daniel Dadush et al. demonstrated in On circuit diameter bounds via circuit imbalances that augmentation algorithms can solve LPs in a strongly polynomial number of steps relative to the logarithm of the "circuit imbalance."
By shifting the complexity metric from the raw precision of the input data ($L$) to the structural, combinatorial properties of the constraints, this line of research provides the closest approximation yet to a truly strongly polynomial linear programming framework.
Key Foundational Work
Probabilistic analysis of a differential equation for linear programming (2003) — contributed 1 concept elements to this direction.
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time (2004) — contributed 1 concept elements to this direction.