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 to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for Zadeh's pivoting rule [25]. Also known as the Least-Entered rule, Zadeh's pivoting method belongs to the family of memorizing improvement rules, which among all improving pivoting steps from the current basic feasible solution (or vertex) chooses one which has been entered least often. We provide the first subexponential (i.e., of the form 2~(Ω(1))) lower bound for this rule. Our lower bound is obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. We start by building 2-player parity games (PGs) on which the policy iteration with the Least-Entered rule performs a subexponential number of iterations. We then transform the parity games into 1-player Markov Decision Processes (MDPs) which corresponds almost immediately to concrete linear programs.