A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games

摘要: The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most pivoting rules are known, however, to need an exponential number of steps solve some programs. No non-polynomial lower bounds were prior this work, Zadeh's rule [25]. Also known as Least-Entered rule, method belongs family memorizing improvement rules, which all improving from current basic feasible solution (or vertex) chooses one has been entered least often. We provide first subexponential (i.e., form 2Ω(√n) bound rule. Our obtained by utilizing connections between performed simplex-based and switches policy iteration 1-player 2-player games. start building parity games (PGs) on with LEAST-ENTERED performs a iterations. then transform into Markov Decision Processes (MDPs) corresponds almost immediately concrete