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…