An improved Kalai-Kleitman bound for the diameter of a polyhedron

Kalai and Kleitman 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)}$.

Citation

School of Operations Research and Information Engineering, Cornell University, Ithaca NY, USA, February 2014

Article

Download

View PDF