An improved Kalai-Kleitman bound for the diameter of a polyhedron. (English) Zbl 1316.52021
Summary: G. Kalai and D. J. Kleitman [Bull. Am. Math. Soc., New Ser. 26, No. 2, 315–316 (1992; Zbl 0751.52006)] established the bound \(n^{\log(d) + 2}\) for the diameter of a \(d\)-dimensional polyhedron with \(n\) facets. Here, we improve the bound slightly to \((n-d)^{\log(d)}\).
MSC:
52B11 | \(n\)-dimensional polytopes |
90C05 | Linear programming |
52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |