Discrete Math Seminar Fall 2008
The Hirsch conjecture and 0/1 polytopes
Christine Kelley, UNL;
Sept 2
In 1957 Hirsch conjectured that the maximum diameter of a
d-dimensional polyhedron with n facets is at most n - d. This result is of
practical importance, as the maximum diameter relates to the complexity of
many combinatorial optimization algorithms. Starting with a background on
polytopes, we will discuss the Hirsch conjecture and its equivalent
formulations, and then look at Naddef's proof that the Hirsch conjecture
is true for the class of 0/1 polytopes.