2022-05-27
On circuit diameter bounds via circuit imbalances
Publication
Publication
Presented at the
23rd International Conference on Integer Programming and Combinatorial Optimization (2022) - IPCO 2022 (June 2022), Eindhoven, The Netherlands
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.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-031-06901-7_11 | |
| Lecture Notes in Computer Science | |
| Towards a Quantitative Theory of Integer Programming | |
| 23rd International Conference on Integer Programming and Combinatorial Optimization (2022) - IPCO 2022 | |
| Organisation | Networks and Optimization |
|
Dadush, D., Koh, Z. K., Natura, B., & Végh, L. (2022). On circuit diameter bounds via circuit imbalances. In Integer Programming and Combinatorial Optimization (pp. 140–153). doi:10.1007/978-3-031-06901-7_11 |
|
