The complexity of Zadeh's Pivot Rule / / Alexander Vincent Hopp.

• VerfasserIn: Hopp, Alexander Vincent,
• Place / Publishing House: Germany : : Logos Verlag Berlin,, [2020]; ©2020
• Year of Publication: 2020
• Edition: First edition.
• Language: English
• Physical Description: 1 online resource (xvi, 319 pages) :; illustrations; digital file(s).

The question whether linear programs can be solved in strongly polynomial time is a majoropen problem in the field of optimization. One promising candidate for an algorithm thatpotentially guarantees to solve any linear program in such time is the simplex algorithmof George Dantzig. This algorithm can be parameterized by a pivot rule, and providing apivot rule guaranteeing a polynomial number of iterations in the worst case would resolvethis open problem.For all known classical natural pivot rules, superpolynomial lower bounds have beendeveloped. Starting with the famous Klee-Minty cube, a series of exponential lower boundconstructions have been developed for a majority of pivot rules. There were, however,two classes of pivot rules whose worst-case behavior remained unclear for a long time –randomized and memorizing rules.Only in the 2010s, the works of Fearnley, Friedmann, Hansen and their colleaguesprovided superpolynomial bounds for those rules, starting a second series of lower bounds.The arguably most remarkable of these bounds was Friedmann’s construction for whichZadeh’s LeastEntered pivot rule requires at least a subexponential number of iterations.This pivot rule is the main focus of this thesis. Following the work of Friedmann, weintroduce parity games, Markov decision processes and linear programs and investigatecertain subclasses of the first two structures. We discuss connections between these threeframeworks, generalize previous definitions and provide a clean framework for workingwith so-called sink games and weakly unichain Markov decision processes.We then revisit Friedmann’s subexponential lower bound and discuss several of itstechnical aspects in full detail and exhibit several flaws in his analysis. The most severe isthat the sequence of steps performed by Friedmann does not consistently obey Zadeh’spivot rule. We resolve this issue by providing a more sophisticated sequence of steps,which is in accordance with the pivot rule, without changing the macroscopic structure ofFriedmann’s construction.The main contribution of this thesis is the newest member of the second wave of lowerbound examples – the first exponential lower bound for Zadeh’s pivot rule. This closes along-standing open problem by ruling out this pivot rule as a candidate for a deterministic,subexponential pivot rule in several areas of linear optimization and game theory.

Table of Contents

1. Introduction -- 2. Preliminaries -- 3. Strategy Improvement and Policy Iteration -- 4. On Friedmann’s Subexponential Lower Bound for Zadeh’s Pivot Rule -- 5. An Exponential Lower Bound for Zadeh’s Pivot Rule -- 6. Technical Details of the Exponential Lower Bound Construction -- 7. Conclusion -- Bibliography -- Index -- Curriculum Vitae