Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2 Ω(n α ) , for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

Authors

• Oliver Friedmann
• Thomas Dueholm Hansen
• Uri Zwick

Keywords

• randomized pivoting rules
• Markov decision processes
• simplex algorithm
• linear programming