×

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.)

Citations:

Zbl 0751.52006