Upper bounds for the diameter and height of graphs of convex polyhedra

Abstract

Let Δ(d, n) be the maximum diameter of the graph of a d-dimensional polyhedron P with n-facets. It was conjectured by Hirsch in 1957 that Δ(d, n) depends linearly on n and d. However, all known upper bounds for Δ(d, n) were exponential in d. We prove a quasi-polynomial bound Δ(d, n)≤n2 log d+3. Let P be a d-dimensional polyhedron with n facets, let φ{symbol} be a linear objective function which is bounded on P and let v be a vertex of P. We prove that in the graph of P there exists a monotone path leading from v to a vertex with maximal φ{symbol}-value whose length is at most {Mathematical expression}. © 1992 Springer-Verlag New York Inc.