158 citations · 543 across the 80 of their papers we have counts for
Showing 2003Show all
2 papers · 1 filter
math.CO2003
The Simplex Algorithm in Dimension Three
Volker Kaibel, Rafael Mechtel, Micha Sharir +1
We investigate the worst-case behavior of the simplex algorithm on linear programs with three variables, that is, on 3-dimensional simple polytopes. Among the pivot rules that we c…
math.CO2003★ 1 cited
The Random Edge Rule on Three-Dimensional Linear Programs
Volker Kaibel, Raphael Mechtel, Micha Sharir +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 b…