math_groups_discgeom

The random-edge rule on three-dimensional linear programs

Volker Kaibel and Rafael Mechtel and Micha Sharir and Günter M. Ziegler

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.

TitelThe random-edge rule on three-dimensional linear programs
VerfasserVolker Kaibel and Rafael Mechtel and Micha Sharir and Günter M. Ziegler
Quelle/n
ArtText