On Circuit Diameter Bounds via Circuit Imbalances

Daniel Dadush, Zhuan Khye Koh, Bento Natura, László A. Végh

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\leq x\leq u\}$ for $A \in \mathbb{R}^{m \times n}$ is bounded as $O(m \min\{m, n-m\} \log(m+ \kappa_A)+n \log n)$, where $\kappa_A$ is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound e.g. if 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))$ augmentation steps.
BibTeX
@inproceedings{dadush2022circuit,
  author = {Daniel Dadush and Zhuan Khye Koh and Bento Natura and László A. Végh},
  title = {{On Circuit Diameter Bounds via Circuit Imbalances}},
  booktitle = {IPCO},
  year = {2022},
  doi = {10.1007/978-3-031-06901-7\_11},
}
Figure