On circuit diameter bounds via circuit imbalances

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 for is bounded by , where 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 augmentation steps.

• View at arXiv

Free Full Text ( Final Version , 1mb )

See Also
inProceedings On circuit diameter bounds via circuit imbalances D.N. Dadush (Daniel), Z.K. Koh (Zhuan Khye), B. Natura (Bento) and L.A. Végh (László)