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
Additional Services
| 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 |
