On Circuit Diameter Bounds via Circuit Imbalances

Abstract

We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIDMA 2015) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system $\{x\in {\mathbb{R}}^n:Ax=b,0\le x\le u\}$ for $A\in {\mathbb{R}}^{m\times n}$ is bounded by $O(m\min \{m,n-m\}\log (m+\hat{I}{º}_A)+n\log n)$, where $\hat{I}{º}_A$ is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound if e.g., all entries of $A$ have polynomially bounded encoding length in $n$. Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an LP in $O(m{n}^2\log (n+\hat{I}{º}_A))$ augmentation steps.