Linear programming is the problem of minimizing a linear
objective function F on d variables subject to n linear inequalities. The set of
feasible solutions to a linear programming problem is a polyhedron P in R^d. The
(0-dimensional) vertices and (1-dimensional) edges of this polyhedron P form a
graph G. This graph G can be made directed by orienting every edge from the
endpoint with the larger value of F to the endpoint with the smaller value. To
solve a linear programming problem, the simplex algorithm starts at an arbitrary
vertex of G and then greedily follows a directed path in G up to the local
minimum, the sink, which happens to be the global minimum as well. Different
variants of the simplex algorithm are obtained by applying different local
greedy choices when building the path.
While linear programming is solvable in polynomial time in the worst case (using
the ellipsoid or the interior method), no variant of the simplex algorithm has
been shown to run in polynomial time in the worst case. In fact, no
deterministic greedy choice has been shown to give a sub-exponential algorithm,
and it was a breaktrough when in the early 1990s, Kalai, and Matousek, Sharir
and Welzl independently presented sub-exponential, randomized simplex
algorithms.
What is baffling is that, on real world problems, the simplex algorithm runs
almost always in linear time. Furthermore, it is believed (though still an open
question) that the diameter D of G is linear in n as well: Hirsh conjectured,
way back in 1957, that D <= n - d. However, the best known upper bound on D is
only quasi-polynomial: the n^{log d + 1} bound from 1992 by Kalai and Kleitman.
In this talk, I will review Kalai's and Matousek, Sharir, and Welzl's randomized
subexponential variants of the simplex algorithm, and prove Kalai and Kleitman's
quasi-polynomial bound on the diameter of G. I will then discuss a string of
more recent papers that suggest that a better understanding of the structure of
the directed graph G will be essential to any attempt to obtain a polynomial
time simplex algorithm.