The complexity of the simplex method

DOI10.1145/2746539.2746558MaRDI QIDQ2941508zbMATH OpenOpenAlexFDO

Authors John Fearnley, Rahul Savani

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.0605

zbMATH Keywords

linear programmingMarkov decision processespolicy iterationsimplex methodDantzig's pivot rule

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40)

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 show PSPACE-completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.

Recommendations

• On Simplex Pivoting Rules and Complexity Theory
• The simplex method is strongly polynomial for deterministic Markov decision processes
• The simplex method is strongly polynomial for deterministic Markov decision processes
• The Complexity of Zadeh's Pivot Rule

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(27)

• The simplex method is strongly polynomial for deterministic Markov decision processes
• scientific article; zbMATH DE number 653033 (Why is no real title available?)
• Optimal pivot path of the simplex method for linear programming based on reinforcement learning
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• What is the worst case behavior of the simplex algorithm?
• The complexity of all-switches strategy improvement
• On Simplex Pivoting Rules and Complexity Theory
• On the Complexity of Value Iteration
• Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm
• Simplex pivots on the set packing polytope
• Automatic verification of concurrent stochastic systems
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• On the length of monotone paths in polyhedra
• Pivot rules for circuit-augmentation algorithms in linear optimization
• scientific article; zbMATH DE number 4156195 (Why is no real title available?)
• The Polyhedral Geometry of Pivot Rules and Monotone Paths
• The simplex method is not always well behaved
• An exponential lower bound for Zadeh's pivot rule
• An overview on the simplex algorithm
• Computational techniques of the simplex method
• The simplex method is strongly polynomial for deterministic Markov decision processes
• On Friedmann's subexponential lower bound for Zadeh's pivot rule
• Inapproximability of shortest paths on perfect matching polytopes
• The smoothed complexity of policy iteration for Markov decision processes
• On the complexity of optimization over the standard simplex
• Reinforcement learning of simplex pivot rules: a proof of concept
• scientific article; zbMATH DE number 3852781 (Why is no real title available?)

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: The complexity of the simplex method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941508)