The Simplex-Algorithm in Dimension Three

reasons: For computational purposes it is still the most efficient
general tool for solving linear programs, from a complexity point of
view it is the most promising candidate for a strongly polynomial time
linear programming algorithm, and last but not least, geometers are
pleased by its inherent use of the structure of convex polytopes. This
talk aims at a rather modest goal: To understand the behavior of
various well-known pivot-rules for the Simplex-Algorithm in the case
of three variables. The results on worst-case running times that we
prove reveal a winner, which despite (or due to?) its simplicity is
also considered a candidate for yielding a polynomial time algorithm
in general dimension. Our treatment may also serve as a survey on
several pivot-rules for the Simplex-Algorithm, including some not so
well-known ones that up to now have resisted against fooling them by
hard examples of linear programs.
The talk is based on joint work with Rafael Mechtel, Micha Sharir,
and Günter M. Ziegler.