The Random Edge Rule on Three-Dimensional Linear Programs

Volker Kaibel , Raphael Mechtel , Micha Sharir , G\"unter M. Ziegler

Authors on Pith no claims yet

classification 🧮 math.CO math.OC

keywords edgelinearrandomrulealgorithmboundedconstraintsdimensional

read the original abstract

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.

This paper has not been read by Pith yet.

The Random Edge Rule on Three-Dimensional Linear Programs

discussion (0)