The complexity of the simplex method

DOI10.1145/2746539.2746558zbMATH Open1321.90079arXiv1404.0605OpenAlexW2061874298MaRDI QIDQ2941508FDOQ2941508

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)

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.

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

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

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)

Cites Work

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

Cited In (28)

• The simplex method is strongly polynomial for deterministic Markov decision processes
• Title not available (Why is that?)
• 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
• The simplex algorithm is NP-mighty
• On Simplex Pivoting Rules and Complexity Theory
• On the Complexity of Value Iteration
• Simplex pivots on the set packing polytope
• Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm
• 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
• The Polyhedral Geometry of Pivot Rules and Monotone Paths
• Title not available (Why is that?)
• An exponential lower bound for Zadeh's pivot rule
• The simplex method is not always well behaved
• An overview on the simplex algorithm
• The simplex method is strongly polynomial for deterministic Markov decision processes
• Computational techniques of the simplex method
• Inapproximability of shortest paths on perfect matching polytopes
• On Friedmann's subexponential lower bound for Zadeh's pivot rule
• 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
• Title not available (Why is that?)

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)