An asymptotically improved upper bound on the diameter of polyhedra
From MaRDI portal
Publication:2324633
DOI10.1007/s00454-018-0016-yzbMath1423.52018OpenAlexW2809374263MaRDI QIDQ2324633
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
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
