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

zbMATH Keywords

isoperimetric inequality; total unimodularity; totally unimodular matrices; diameter of polyhedra; polyhedral graph

Mathematics Subject Classification ID

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

Stable Clusterings and the Cones of Outer Normals, Good Clusterings Have Large Volume, On the Length of Monotone Paths in Polyhedra, Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles, Formalizing the Face Lattice of Polyhedra, On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases, A Friendly Smoothed Analysis of the Simplex Method, On sub-determinants and the diameter of 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, 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, On the diameter of lattice polytopes, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Primitive zonotopes, On the shadow simplex method for curved polyhedra, 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, The diameters of network-flow polytopes satisfy the Hirsch conjecture, On the recognition of \(\{a,b,c\}\)-modular matrices, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles, Notes on \(\{a,b,c\}\)-modular matrices, On lattice point counting in \(\varDelta\)-modular polyhedra, On circuit diameter bounds via circuit imbalances, A note on the diameter of convex polytope, A scaling algorithm for optimizing arbitrary functions over vertices of polytopes, An asymptotically improved upper bound on the diameter of polyhedra, Improving bounds on the diameter of a polyhedron in high dimensions, Geometric random edge, Circuit walks in integral 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

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