We provide the first subexponential lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. The first randomized pivoting rule we consider is Random-Edge, which among all improving pivoting steps from the current basic feasible solution chooses one uniformly at random. The second randomized pivoting rule we consider is Random-Facet, a more complicated recursive randomized pivoting rule. Lower bounds for Random-Edge and Random-Facet were known before only in abstract settings, and not for concrete linear programs. We also give a lower bound for Zadeh’s pivoting rule which among all improving pivoting steps enters the variable that has been entered least often.
Our lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for Markov Decision processes (MDP). We build MDPs on which suitable policy iteration algorithms perform a subexponential number of iterations, and then show that they correspond to concrete linear programs.
Copyright. All Rights Reserved.