On Simplex Pivoting Rules and Complexity Theory

DOI10.1007/978-3-319-07557-0_2MaRDI QIDQ5418981zbMATH OpenOpenAlexFDO

Authors Ilan Adler, Aviad Rubinstein, Christos Papadimitriou

Publication date 2 June 2014

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitylinear programmingsimplex method

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

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.

Recommendations

• scientific article; zbMATH DE number 3904322
• On the complexity of a pivot step of the revised simplex algorithm
• scientific article; zbMATH DE number 653033
• scientific article; zbMATH DE number 4027159
• Simplicial pivoting algorithms for a tractable class of integer programs
• The Complexity of Zadeh's Pivot Rule
• On the complexity of optimization over the standard simplex
• The complexity of the simplex method
• A note on the Edmonds-Fukuda pivoting rule for simplex algorithms
• scientific article; zbMATH DE number 1960976

Cited in

(20)

• Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
• Green scheduling, flows and matchings
• Goldfarb's cube
• The complexity of the simplex method
• On the Complexity of Breaking Pseudoentropy
• scientific article; zbMATH DE number 3904322 (Why is no real title available?)
• The complexity of all-switches strategy improvement
• On the length of monotone paths in polyhedra
• The Complexity of Zadeh's Pivot Rule
• Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Monotone diameter of bisubmodular polyhedra
• The Polyhedral Geometry of Pivot Rules and Monotone Paths
• Inapproximability of shortest paths on perfect matching polytopes
• 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
• 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
• Practical finite pivoting rules for the simplex method

This page was built for publication: On Simplex Pivoting Rules and Complexity Theory

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