Math Conjectures

Polynomial pivot rule for the simplex method

OPENLandmarkOpen problemProposed c. 1972 · Standard version

Canonical statement

There exist a deterministic or randomized simplex pivot rule and a polynomial pp such that, for every bounded nondegenerate rational linear program
max⁡{cTx:Ax=b, x≥0},A∈Qm×n, \max\{c^{\mathsf T}x:Ax=b,\ x\ge0\},\qquad A\in\mathbb Q^{m\times n},
and every feasible starting basis, the simplex method using that rule reaches an optimal basis after at most p(m,n)p(m,n) pivots (in expectation over the rule's randomness in the randomized case).
View source LaTeX
There exist a deterministic or randomized simplex pivot rule and a polynomial \(p\) such that, for every bounded nondegenerate rational linear program
\[
\max\{c^{\mathsf T}x:Ax=b,\ x\ge0\},\qquad A\in\mathbb Q^{m\times n},
\]
and every feasible starting basis, the simplex method using that rule reaches an optimal basis after at most \(p(m,n)\) pivots (in expectation over the rule's randomness in the randomized case).
OPT-002:[KleeMinty1972Simplex][Kalai1992Subexponential][FriedmannHansenZwick2011Pivot]
Mathematical optimizationOperations research

Notes

The simplex method moves from basis to basis according to a pivot rule, and in practice it terminates quickly; the question is whether some rule provably requires only polynomially many pivots on every linear program, deterministically or in expectation. The problem was put in sharp form by Klee and Minty in 1972, whose deformed cubes force the classical Dantzig rule to take exponentially many steps [KleeMinty1972Simplex].

Exponential worst-case constructions were subsequently found for essentially all classical deterministic pivot rules. On the positive side, Kalai gave a randomized pivot rule with a subexponential expected number of pivots [Kalai1992Subexponential], and subexponential bounds remain the best general guarantees known. Friedmann, Hansen, and Zwick then showed that widely studied randomized rules themselves admit subexponential lower bounds [FriedmannHansenZwick2011Pivot], so randomness alone does not obviously suffice. The question is not equivalent to strongly polynomial linear programming: a strongly polynomial algorithm need not follow polytope edges, and a pivot-count bound alone does not control all arithmetic costs.

No polynomial pivot rule is known and none has been excluded; the problem remains open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.