Abstract
Let Δ(d, n) be the maximum diameter of the graph of ad-dimensional polyhedronP withn-facets. It was conjectured by Hirsch in 1957 that Δ(d, n) depends linearly onn andd. However, all known upper bounds for Δ(d, n) were exponential ind. We prove a quasi-polynomial bound Δ(d, n)≤n 2 logd+3.
LetP be ad-dimensional polyhedron withn facets, let ϕ be a linear objective function which is bounded onP and letv be a vertex ofP. We prove that in the graph ofP there exists a monotone path leading fromv to a vertex with maximal ϕ-value whose length is at most\(n^{2\sqrt n } \).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.Avoid common mistakes on your manuscript.
References
D. W. Barnette,W v paths on 3-polytopes,J. Combin. Theory 7 (1969), 62–70.
D. B. Dantzig,Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.
A. V. Goldberg, E. Tardos, and R. E. Tarjan, Network flow algorithms, inPath, Flows and VLSI Layout, (B. Korteet al., eds.), Springer-Verlag, New York, 1990, pp. 101–164.
B. Grünbaum,Convex Polytopes, Wiley Interscience, London, 1967, Chapter 16.
G. Kalai, The diameter problem for convex polytopes andf-vector theory, inThe Victor Klee Festschrift (P. Gritzman and B. Strumfels, eds.), American Mathematical Society, Providence, RI, 1991, pp. 387–411.
G. Kalai and D. J. Kleitman, A quasi-polynomial bound for diameter of graphs of polyhedra, Research Announcement,Bull. Amer. Math. Soc. 24 (1992), in press.
V. Klee and P. Kleinschmidt, Thed-steps conjecture and its relatives,Math. Oper. Res. 12 (1987), 718–755.
V. Klee and G. J. Minty, How good is the simplex algorithm? inInequalities, Vol. III (O. Shisha, ed.), Academic Press, New York, 1972, pp. 159–175.
V. Klee and D. Walkup, Thed-step conjecture for polyhedra of dimensiond < 6,Acta Math. 133 (1967), 53–78.
D. G. Larman, Paths on polytopes,Proc. London Math. Soc. 20 (1970), 161–178.
P. McMullen, The maximal number of faces of a convex polytope,Mathematika 17 (1970), 179–184.
G. Kalai, A subexponential randomized simplex algorithm,Proc. 24th ACM Symposium on Theory of Computing, 1992, to appear.
Author information
Authors and Affiliations
Additional information
This research was supported in part by a BSF grant, by a GIF grant, and by ONR-N00014-91-C0026.
Rights and permissions
About this article
Cite this article
Kalai, G. Upper bounds for the diameter and height of graphs of convex polyhedra. Discrete Comput Geom 8, 363–372 (1992). https://doi.org/10.1007/BF02293053
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02293053