On sub-determinants and the diameter of polyhedra

DOI10.1145/2261250.2261304zbMath1293.52008arXiv1108.4272OpenAlexW1996425479MaRDI 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

zbMATH Keywords

isoperimetric inequalitytotal unimodularitytotally unimodular matricesdiameter of polyhedrapolyhedral graph

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Improving bounds on the diameter of a polyhedron in high dimensions, Geometric random edge, On the diameter of lattice polytopes, Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles, Notes on \(\{a,b,c\}\)-modular matrices, Formalizing the Face Lattice of Polyhedra, On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond, On lattice point counting in \(\varDelta\)-modular polyhedra, On circuit diameter bounds via circuit imbalances, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Circuit walks in integral polyhedra, On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases, Advances on strictly \(\varDelta \)-modular IPs, New Bounds for the Integer Carathéodory Rank, On the Combinatorial Diameters of Parallel and Series Connections, On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems, A Friendly Smoothed Analysis of the Simplex Method, A note on the diameter of convex polytope, On sub-determinants and the diameter of polyhedra, A scaling algorithm for optimizing arbitrary functions over vertices of polytopes, Improved bounds on the diameter of lattice polytopes, FPT-algorithms for some problems related to integer programming, A note on non-degenerate integer programs with small sub-determinants, Stable Clusterings and the Cones of Outer Normals, The diameters of network-flow polytopes satisfy the Hirsch conjecture, Primitive zonotopes, On the shadow simplex method for curved polyhedra, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Good Clusterings Have Large Volume, On the recognition of \(\{a,b,c\}\)-modular matrices, An asymptotically improved upper bound on the diameter of polyhedra, On the Length of Monotone Paths in Polyhedra, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

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