An asymptotically improved upper bound on the diameter of polyhedra

DOI10.1007/s00454-018-0016-yzbMath1423.52018OpenAlexW2809374263MaRDI QIDQ2324633

Noriyoshi Sukegawa

Publication date: 11 September 2019

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-018-0016-y

zbMATH Keywords

polyhedradiameterrecursive inequality

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Linear programming (90C05) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Diameters of cocircuit graphs of oriented matroids: an update ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Monotone diameter of bisubmodular polyhedra ⋮ Primitive point packing ⋮ The diameter of lattice zonotopes ⋮ On the Combinatorial Diameters of Parallel and Series Connections ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• On the diameter of lattice polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A counterexample to the Hirsch conjecture
• Primitive zonotopes
• On the shadow simplex method for curved polyhedra
• On the diameter of convex polytopes
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Linear programming, the simplex algorithm and simple polytopes
• Hirsch polytopes with exponentially long combinatorial segments
• Improved bounds on the diameter of lattice polytopes
• A refinement of Todd's bound for the diameter of a polyhedron
• A primal-simplex based Tardos' algorithm
• The Hirsch conjecture is true for (0,1)-polytopes
• Who solved the Hirsch conjecture?
• Improving bounds on the diameter of a polyhedron in high dimensions
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter of Polyhedra: Limits of Abstraction
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• The width of five-dimensional prismatoids
• An Improved Kalai--Kleitman Bound for the Diameter of a Polyhedron
• More bounds on the diameters of convex polytopes
• Paths on Polyhedra. I
• Paths on Polytopes
• Diameters of Polyhedral Graphs
• On sub-determinants and the diameter of polyhedra