Publication
Discrete and Computational Geometry
Paper

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

Download paper

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.

Date

Publication

Discrete and Computational Geometry

Authors

Resources

Share