On Circuit Diameter Bounds via Circuit Imbalances
Lists
Only you see this
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},
}