Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the dimension is 3, and fits better for a high-dimensional polyhedron with a large number of facets.

Citation

Technical report, Tokyo Institute of Technology

Article

Download

View Improvement of Kalai-Kleitman bound for the diameter of a polyhedron