On Simplex Pivoting Rules and Complexity Theory

2014/04/12 by Adler, Ilan, Papadimitriou, Christos, Rubinstein, Aviad · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.1.6

paper · doi:10.48550/arxiv.1404.3320

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.

Cited by

• Lower bounds for ranking-based pivot rules

Related

• The Complexity of the Simplex Method
• Exponential Lower Bounds for Many Pivot Rules for the Simplex Method
• On the Simplex method for 0/1 polytopes
• The existence of a strongly polynomial time simplex algorithm for linear programs
• The Polyhedral Geometry of Pivot Rules and Monotone Paths