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

  • Michael J. Todd
    • Categories Linear Programming Tags , Short URL: https://optimization-online.org/?p=12755

    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 An improved Kalai-Kleitman bound for the diameter of a polyhedron