Two New Bounds on the Random-Edge Simplex Algorithm
| dc.creator | Gärtner, Bernd | |
| dc.creator | Kaibel, Volker | |
| dc.date | 2005-02-01 | |
| dc.date | 2008-07-15 | |
| dc.date.accessioned | 2026-07-07T09:50:16Z | |
| dc.date.available | 2026-07-07T09:50:16Z | |
| dc.description | 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. | |
| dc.description | 10 pages | |
| dc.identifier | https://arxiv.org/abs/math/0502025 | |
| dc.identifier | http://arxiv.org/abs/math/0502025 | |
| dc.identifier | SIAM Journal on Discrete Mathematics 21, 178-190 (2007) | |
| dc.identifier | doi:10.1137/05062370X | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/164885 | |
| dc.subject | Combinatorics | |
| dc.subject | Optimization and Control | |
| dc.subject | 90C05; 68W20 | |
| dc.title | Two New Bounds on the Random-Edge Simplex Algorithm | |
| dc.type | text |