TY - GEN A1 - Gärtner, Bernd A1 - Kaibel, Volker T1 - Two New Bounds for the Random-Edge Simplex Algorithm N2 - 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. Y1 - 2005 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/224 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-2245 ER -