On circuit diameter bounds via circuit imbalances

We study the circuit diameter of polyhedra, introduced by Borgwardt, Finhold, and Hemmecke (SIAM J. Discrete Math. 29(1), 113–121 (2015)) as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system \(\{x\in \mathbb {R}^n:\, Ax=b,\, \mathbb {0}\le x\le u\}\) $\{x\in {\mathbb{R}}^n:Ax=b,\mathbb{0}\le x\le u\}$ for \(A\in \mathbb {R}^{m\times n}\) $A\in {\mathbb{R}}^{m\times n}$ is bounded by \(O(m\min \{m, n - m\}\log (m+\kappa _A)+n\log n)\) $O(mmin\{m,n-m\}log(m+{\kappa }_A)+nlogn)$ , where \(\kappa _A\) ${\kappa }_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(mn^2\log (n+\kappa _A))\) $O(m{n}^{2}log(n+{\kappa }_A))$ augmentation steps.