Department of Computer Science | Institute of Theoretical Computer Science

We prove that the Random-Edge simplex algorithm requires an expected
number of at most 13n/sqrt(d) pivot steps on any simple d-polytope
with n vertices. This is the first nontrivial upper bound for general
polytopes. We also describe a refined analysis that potentially yields
much better bounds for specific classes of polytopes. As one
application, we show that for combinatorial d-cubes, the trivial upper
bound of 2^d on the performance of Random-Edge can asymptotically be
improved by any desired polynomial factor in d.