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

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