Two New Bounds for the Random‐Edge Simplex‐Algorithm
Bernd Gärtner, Volker Kaibel · SIAM Journal on Discrete Mathematics · 2007
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 the factor $1/d^{(1-\varepsilon)\log d}$ for every $\varepsilon>0$.