Two New Bounds for the Random-Edge Simplex Algorithm
Please always quote using this URN: urn:nbn:de:0297-zib-8483
- 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.
Author: | Bernd Gärtner, Volker Kaibel |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 2005/02/04 |
Series (Serial Number): | ZIB-Report (05-14) |
ZIB-Reportnumber: | 05-14 |
Published in: | Appeared in: SIAM J. Discr. Mathematics 21 (2007) 178-190 |