This guest post on The Mathematics of Klee and Grünbaum 2010 is by CR reviewer Joseph O'Rourke, Professor and Chair of the Computer Science Department at Smith College.
This conference in honor of the mathematical contributions of Victor Klee and Branko Grünbaum, held July 28-30, 2010, was subtitled “100 years in Seattle” because, in sum, they have been professors at the University of Washington that long. Victor Klee passed away in 2007, but Grünbaum was present and actively participated in the talks with his penetrating questions and observations. This was a pure mathematics conference, concentrating on their specialties in geometry and combinatorics. Few computer scientists were in attendance, but the topics nevertheless are quite relevant to computer science.
The nature of the conference led to a wide range of talks not easily summarized. Instead, I will concentrate on the most spectacular result presented: Francisco Santos’ description of his recent counterexample to the Hirsch conjecture. This conjecture says that the diameter of a convex polytope of n facets in d dimensions is at most n − d. Here, the diameter is the longest path of edges between any two facets of the polytope. It was proved for d ≤ 3, but stood unresolved for 50 years before Santos cracked the problem in the spring of 2010. Aside from its mathematical interest, this conjecture is important because the simplex method for solving a linear program walks along a path on the surface of a polytope (often in dimensions as large as d = 10000). So the diameter of the polytope provides a lower bound on its worst-case complexity, and establishing an upper bound on the diameter raises that complexity lower bound.
Santos’ smallest counterexample is a 38-dimensional polytope of 76 facets, so n−d = 76−38 = 38; but its diameter is 39, +1 beyond the conjectured bound. Using this example, he can build polytopes that violate the conjecture by a factor of (1 + ε) for any ε > 0 and fixed dimension d. His counterexample is based on the construction of what he calls a “spindle” polytope in five dimensions, which derives, appropriately enough, from the work of Victor Klee. Due to the importance of his result, Santos supplemented his convincing proofs with computational verification. There is no question: the Hirsch conjecture has been settled negatively. (And Grünbaum needs to update his masterwork Convex Polytopes again!)
Where that leaves us was nicely described in Gil Kalai’s talk at the conference on the “polynomial Hirsch conjecture,” which states that the diameter is bounded by some polynomial in d and n. It is a remarkable indication of our ignorance of convex polytopes that we cannot bound their diameter by, say, n100 d100. The best upper bounds are nlogd+1 and n2d−3: quasi-polynomial and linear for d fixed (but remember: d can be large). It is curious that the behavior of one of the most successful and heavily used algorithms of all time—the simplex method—remains mysterious. Perhaps this breakthrough on the diameter of polytopes will eventually lead to a dispelling of this mystery.
(Above photo credit: https://sites.google.com/a/alaska.edu/kleegrunbaum/)
Comments