pipette
ENEnglish

Parametrize Integer Programming by Packing Imbalanced Circuits

Yuheng Shi

Preprint

En palabras de los autores

We study the standard form Integer Programming problem (IP) parametrized by the imbalanced circuit packing number. This number is if and only if can be transformed to a totally unimodular matrix by row operations, in which case (IP) is solvable in polynomial time. We show that if the constraint matrix represents a graphic matroid, (IP) is fixed-parameter tractable when parametrized by the imbalanced circuit packing number of the matrix. The proof combines an Erd\H{o}s-P\'osa property for edge-colored non-monochromatic cycles with a reduction to mixed-integer programming using few integer variables. In contrast, by a reduction from the parity potential problem, we show NP-completeness of feasibility of (IP) when the constraint matrix represents a cographic matroid, even if kernel of the constraint matrix is -regular and imbalanced circuits pairwise intersect.

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.