Subexponential lower bounds for randomized pivoting rules for the simplex algorithm – Københavns Universitet

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Guest lecture with professor Uri Zwick, Tel Aviv University 


The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are 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^{\Omega(n^\alpha)}$, for some $\alpha>0$) 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 (or edges) from the current basic  feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule we consider is Random-Facet, a more complicated randomized pivoting rule suggested by Kalai (1992) and Matou{\v{s}}ek, Sharir and Welzl (1996).

Our lower bound for the Random-Facet pivoting rule essentially matches the subexponential upper bounds of Kalai and Matou{\v{s}}ek et al. Lower bounds for Random-Edge and Random-Facet were known before only in abstract settings, and not for concrete linear programs.


Uri Zwick is a leading capacity within research in algorithms. He received his B.Sc. degree in Computer Science from the Technion, Israel Institute of Technology, and his M.Sc. and Ph.D. degrees in Computer Science from Tel Aviv University.

He is currently a Professor of Computer Science in Tel Aviv University. His main research interests are: algorithms and complexity, combinatorial optimization, mathematical games, and recreational mathematics.