On sub-determinants and the diameter of polyhedra
DOI10.1145/2261250.2261304zbMath1293.52008arXiv1108.4272MaRDI QIDQ5891422
Martin Niemeier, Marco Di Summa, Nicolas Bonifas, Friedrich Eisenbrand, Nicolai Hähnle
Publication date: 7 August 2014
Published in: Discrete \& Computational Geometry, Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.4272
isoperimetric inequality; total unimodularity; totally unimodular matrices; diameter of polyhedra; polyhedral graph
52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B11: (n)-dimensional polytopes
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
52A38: Length, area, volume and convex sets (aspects of convex geometry)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A counterexample to the Hirsch conjecture
- An update on the Hirsch conjecture
- A linear bound on the diameter of the transportation polytope
- Graphs of transportation polytopes
- An upper bound for the diameter of a polytope
- The dimension of almost spherical sections of convex bodies
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- A polynomial time primal network simplex algorithm for minimum cost flows
- Logarithmic convexity and inequalities for the gamma function
- The Hirsch conjecture is true for (0,1)-polytopes
- The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
- Diameter of Polyhedra: Limits of Abstraction
- The Hirsch Conjecture for Dual Transportation Polyhedra
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- A quasi-polynomial bound for the diameter\\of graphs of polyhedra
- Random walks in a convex body and an improved volume algorithm
- Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
- Paths on Polytopes
- On sub-determinants and the diameter of polyhedra