Paper Info
Title
The Complexity of the Simplex Method.
Abstract
The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE-complete to find the solution that is computed by the simplex method using Dantzig's pivot rule. Secondly, we prove that deciding whether Dantzig's rule ever chooses a specific variable to enter the basis is PSPACE-complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig's pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and then show PSPACE-completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.
Year
DOI
Venue
2014
10.1145/2746539.2746558
symposium on the theory of computing
Keywords
Field
DocType
markov decision processes,linear programming
Mathematical optimization,Combinatorics,Reduced cost,Simplex algorithm,Revised simplex method,Markov decision process,Equivalence (measure theory),Linear programming,Linear complementarity problem,Klee–Minty cube,Mathematics
Journal
Volume
ISSN
Citations 
abs/1404.0605
0737-8017
5
PageRank 
References 
Authors
0.47
19
2
Name
Order
Citations
PageRank
John Fearnley113417.49
Rahul Savani224330.09