On Simplex Pivoting Rules and Complexity Theory

Abstract

We show that there are simplex pivoting rules for which it is PSPACE-complete to tell if a particular basis will appear on the algorithm's path. Such rules cannot be the basis of a strongly polynomial algorithm, unless P = PSPACE. We conjecture that the same can be shown for most known variants of the simplex method. However, we also point out that Dantzig's shadow vertex algorithm has a polynomial path problem. Finally, we discuss in the same context randomized pivoting rules.

To appear in IPCO 2014

Cited by in corpus (2)

• The Complexity of the Simplex Method
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problem