arXiv Analytics

Sign in

arXiv:math/0301076 [math.CO]AbstractReferencesReviewsResources

The Random Edge Rule on Three-Dimensional Linear Programs

Volker Kaibel, Raphael Mechtel, Micha Sharir, Günter M. Ziegler

Published 2003-01-09Version 1

The worst-case expected length f(n) of the path taken by the simplex algorithm with the Random Edge pivot rule on a 3-dimensional linear program with n constraints is shown to be bounded by 1.3445 n <= f(n) <= 1.4943 n for large enough n.

Comments: 21 pages (10 pages extended abstract + 11 pages appendix)
Categories: math.CO, math.OC
Subjects: 90C05, 52B10, 68W20
Related articles: Most relevant | Search more
arXiv:math/0309351 [math.CO] (Published 2003-09-22, updated 2004-08-20)
The Simplex Algorithm in Dimension Three
arXiv:1308.0454 [math.CO] (Published 2013-08-02, updated 2014-12-21)
Tropicalizing the simplex algorithm
arXiv:2307.05246 [math.CO] (Published 2023-07-11)
Polytope Extensions with Linear Diameters

Links

Toolbox