• search hit 25 of 1114
Back to Result List

Two New Bounds for the Random-Edge Simplex Algorithm

Please always quote using this URN:urn:nbn:de:0296-matheon-2245
  • We prove that the Random-Edge simplex algorithm requires an expected number of at most 13n/pd 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 2d 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
Metadaten
Author:Bernd Gärtner, Volker Kaibel
URN:urn:nbn:de:0296-matheon-2245
Referee:Günter M. Ziegler
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/02/16
Release Date:2005/02/15
Preprint Number:216
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.