Linear Programming, Polyhedra, and The Simplex Algorithm

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.