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,\, \mathbb {0}\le x\le u\}$$ for $$A\in \mathbb {R}^{m\times n}$$ is bounded by $$O(m^2\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 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(n^3\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