The Random Edge Rule on Three-Dimensional Linear Programs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
21 pages (10 pages extended abstract + 11 pages appendix)

Keywords

Combinatorics, Optimization and Control, 90C05; 52B10; 68W20

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/66211

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0301076
 http://arxiv.org/abs/math/0301076

Collections

arXiv