Diameter of polyhedra: limits of abstraction

DOI10.1287/MOOR.1100.0470MaRDI QIDQ3169119zbMATH OpenOpenAlexWikidataFDO

Authors Friedrich Eisenbrand, Nicolai Hähnle, Thomas Rothvoß, Alexander Razborov

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL http://infoscience.epfl.ch/record/164208

zbMATH Keywords

asymptotic boundconvex geometrydiameterdisjoint coveringsHirsch conjecturepolyhedra

Mathematics Subject Classification ID

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

Recommendations

• Diameter of polyhedra: limits of abstraction
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Recent results around the diameter of polyhedra
• Upper bounds for the diameter and height of graphs of convex polyhedra
• Improving bounds on the diameter of a polyhedron in high dimensions

Cited in

(23)

• On the complexity of computing the diameter of a polytope
• Hirsch polytopes with exponentially long combinatorial segments
• Superlinear subset partition graphs with dimension reduction, strong adjacency, and endpoint count
• On the diameter of dual graphs of Stanley-Reisner rings and Hirsch type bounds on abstractions of polytopes
• On the circuit diameter conjecture
• Diameters of cocircuit graphs of oriented matroids: an update
• Distance between vertices of lattice polytopes
• An asymptotically improved upper bound on the diameter of polyhedra
• Improving bounds on the diameter of a polyhedron in high dimensions
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Polyhedral graph abstractions and an approach to the linear Hirsch conjecture
• Obstructions to weak decomposability for simplicial polytopes
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• scientific article; zbMATH DE number 1182910 (Why is no real title available?)
• A counterexample to the Hirsch conjecture
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• The Hirsch conjecture holds for normal flag complexes
• More bounds on the diameters of convex polytopes
• Diameter of polyhedra: limits of abstraction
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Asymptotic bounds on the combinatorial diameter of random polytopes
• On the circuit diameter conjecture for counterexamples to the Hirsch conjecture

This page was built for publication: Diameter of polyhedra: limits of abstraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169119)