Hirsch conjecture

From Wikipedia, the free encyclopedia

In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the generally false statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n  d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n  d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957[1][2] and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method.

The Hirsch conjecture was proven for d < 4 and for various special cases.[3] The best known upper bounds showed only that polytopes have sub-exponential diameter as a function of n and d.[4] After more than fifty years, a counter-example was announced in May 2010 by Francisco Santos, from the University of Cantabria.[5][6][7] The result was presented at the conference 100 Years in Seattle: the mathematics of Klee and Grünbaum and appeared in Annals of Mathematics.[8] Specifically, the paper presented a 43-dimensional polytope of 86 facets with a diameter of more than 43. The counterexample has no direct consequences for the analysis of the simplex method, as it does not rule out the possibility of a larger but still linear or polynomial number of steps.

Various equivalent formulations of the problem had been given, such as the d-step conjecture, which states that the diameter of any 2d-facet polytope in d-dimensional Euclidean space is no more than d.[1][9]

Notes

  1. 1.0 1.1 Ziegler (1994), p. 84.
  2. Dantzig (1963), pp. 160 and 168.
  3. E.g. see Naddef (1989) for 0-1 polytopes.
  4. Kalai & Kleitman (1992).
  5. Santos (2010).
  6. Kalai (2010).
  7. http://gaussianos.com/francisco-santos-encuentra-un-contraejemplo-que-refuta-la-conjetura-de-hirsch/
  8. Santos (2011)
  9. Klee & Walkup (1967).

References

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.