Thursday, November 5, 2009

Long-delayed Posts I: the Hirsch Conjecture

In Lecture 16, when we'd mentioned the simplex algorithm, I'd mumbled something about the diameter of polytopes and the Hirsch conjecture --- here are some details.

If you consider a polyhedron defined in d dimensions by the intersection of n half-spaces, then the Hirsch conjecture says that the diameter of the 1-skeleton of such a polyhedron is at most n-d. We've been using n dimensions (variables) and m half-spaces (constraints), but I will stick with the n,d notation --- you can do the translation. Kalai and Kleitman showed (in this two-page paper) that the diameter is at most n^{2 + log d} --- and this is essentially the best result known.

This problem was of interest to us, because if the diameter of some LP polytope were indeed large, then the simplex algorithm starting from a bad vertex might require a large number of steps. Of course, we only care about polynomiality, so we would be happy with the polynomial Hirsch conjecture: the diameter of the 1-skeleton is at most poly(n,d).

Some more resources:

No comments:

Post a Comment