Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Bernd Gärtner, Volker Kaibel
Document Type:ZIB-Report
Date of first Publication:2005/02/04
Series (Serial Number):ZIB-Report (05-14)
Published in:Appeared in: SIAM J. Discr. Mathematics 21 (2007) 178-190
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.