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∈R n:Ax=b,0≤x≤u} for A∈R m×n is bounded by O(mmin{m,n-m}log(m+κ A)+nlogn), where κ 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 2log(n+κ A)) augmentation steps.