caa a22 4500 469075058 CHVBK 20180323132933.0 cr unu---uuuuu 170328e19921201xx s 000 0 eng 10.1007/BF02293053 doi (NATIONALLICENCE)springer-10.1007/BF02293053 Kalai Gil Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel aut Upper bounds for the diameter and height of graphs of convex polyhedra [Elektronische Daten] [Gil Kalai] 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 % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVy0df9qqqrpepC0xbbL8F4rqqrFfpeea0xe9Lqpe0x% c9q8qqaqFn0dXdir-xcvk9pIe9q8qqaq-xir-f0-yqaqVeLsFr0-vr% 0-vr0xc8meaabaqaciGacaGaaeqabaWaaeaaeaaakeaacaWGUbWaaW% baaSqabeaacaaIYaWaaOaaaeaacaWGUbaameqaaaaaaaa!3C85! $$n^{2\sqrt n } $$ . Springer-Verlag New York Inc., 1992 Discrete & Computational Geometry Springer New York 8/4(1992-12-01), 363-372 0179-5376 8:4<363 1992 8 454 https://doi.org/10.1007/BF02293053 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02293053 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Kalai Gil Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel aut NATIONALLICENCE 773 0- Discrete & Computational Geometry Springer New York 8/4(1992-12-01), 363-372 0179-5376 8:4<363 1992 8 454 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer