An exponential lower bound for Zadeh’s pivot rule
Open Access
- 19 July 2022
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 199 (1-2) , 865-936
Abstract
The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh’s rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that shows that Zadeh’s rule is in fact exponential in the worst case. Our construction is based on a close relation to the Strategy Improvement Algorithm for Parity Games and the Policy Iteration Algorithm for Markov Decision Processes, and we also obtain exponential lower bounds for Zadeh’s rule in these contexts.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (GSC 233/2)
This publication has 28 references indexed in Scilit:
- A counterexample to the Hirsch ConjectureAnnals of Mathematics, 2012
- A simple polynomial-time rescaling algorithm for solving linear programsMathematical Programming, 2007
- RANDOM EDGE can be exponential on abstract cubesAdvances in Mathematics, 2006
- Solving convex programs by random walksJournal of the ACM, 2004
- Mathematical problems for the next centuryThe Mathematical Intelligencer, 1998
- Linear programming, the simplex algorithm and simple polytopesMathematical Programming, 1997
- A subexponential bound for linear programmingAlgorithmica, 1996
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- Worst case behavior of the steepest edge simplex methodDiscrete Applied Mathematics, 1979
- Notes on Bland’s pivoting rule1978