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