An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron

DOI10.1137/140962310zbMath1316.52021arXiv1402.3579OpenAlexW2040483032MaRDI QIDQ5246095

Michael J. Todd

Publication date: 17 April 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.3579

zbMATH Keywords

polyhedradiametersimplex methodHirsch conjecture

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Linear programming (90C05)

Related Items (17)

Improving bounds on the diameter of a polyhedron in high dimensions ⋮ Distance between vertices of lattice polytopes ⋮ Hirsch polytopes with exponentially long combinatorial segments ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ Monotone diameter of bisubmodular polyhedra ⋮ The diameter of lattice zonotopes ⋮ On the Combinatorial Diameters of Parallel and Series Connections ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ A double-pivot simplex algorithm and its upper bounds of the iteration numbers ⋮ A note on the diameter of convex polytope ⋮ Improved bounds on the diameter of lattice polytopes ⋮ Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count ⋮ A refinement of Todd's bound for the diameter of a polyhedron ⋮ Primitive zonotopes ⋮ Monotone paths in geometric triangulations ⋮ On the shadow simplex method for curved polyhedra ⋮ An asymptotically improved upper bound on the diameter of polyhedra

This page was built for publication: An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron