On sub-determinants and the diameter of polyhedra

2011/08/22 by Nicolas Bonifas, Bonifas, Nicolas, Marco Di Summa +7 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities

paper · pdf · doi:10.48550/arxiv.1108.4272

openalex publication_date 2011/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive a new upper bound on the diameter of a polyhedron P = x ∈ Rⁿ : Ax <= b, where A ∈ Z^m\timesn. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by Δ. More precisely, we show that the diameter of P is bounded by O(Δ² n⁴ log nΔ). If P is bounded, then we show that the diameter of P is at most O(Δ² n³.5 log nΔ). For the special case in which A is a totally unimodular matrix, the bounds are O(n⁴ log n) and O(n³.5 log n) respectively. This improves over the previous best bound of O(m¹6 n³ (log mn)³) due to Dyer and Frieze.

Cited by

• Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure

Related

• A simple proof of tail--polynomial bounds on the diameter of polyhedra
• An improved Kalai-Kleitman bound for the diameter of a polyhedron
• Tail diameter upper bounds for polytopes and polyhedra
• More bounds on the diameters of convex polytopes
• Diameter of Polyhedra: Limits of Abstraction