Improving bounds on the diameter of a polyhedron in high dimensions

Abstract

In 1992, Kalai and Kleitman proved that the diameter of a $d$-dimensional polyhedron with $n$ facets is at most $n^{2+{\log }_{2}d}$. In 2014, Todd improved the Kalai-Kleitman bound to $(n-d{)}^{{\log }_{2}d}$. We improve the Todd bound to $(n-d{)}^{-1+{\log }_{2}d}$ for $n\ge d\ge 7$, $(n-d{)}^{-2+{\log }_{2}d}$ for $n\ge d\ge 37$, and $(n-d{)}^{-3+{\log }_{2}d+O\left(1/d\right)}$ for $n\ge d\ge 1$.

References in corpus (7)

• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Improved bounds on the diameter of lattice polytopes
• Hirsch polytopes with exponentially long combinatorial segments
• On the diameter of lattice polytopes
• Tail diameter upper bounds for polytopes and polyhedra
• An improved upper bound on the diameters of subset partition graphs
• A simple proof of tail--polynomial bounds on the diameter of polyhedra

Cited by in corpus (4)

• Improved bounds on the diameter of lattice polytopes
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers
• A simple proof of tail--polynomial bounds on the diameter of polyhedra
• A note on the diameter of convex polytope