  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 consider, the ``random edge'' rule yields the
best asymptotic behavior as well as the most complicated analysis. All other
rules turn out to be much easier to study, but also produce worse results: Most
of them show essentially worst-possible behavior; this includes both Kalai's
``random-facet'' rule, which without dimension restriction is known to be
subexponential, as well as Zadeh's deterministic history dependent rule, for
which no non-polynomial instances in general dimensions have been found so far.

Combinatorics;Optimization and Control