Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems

Abstract

Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k\ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q\le k\cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup [\frac{1}{f},1]$, for any constant integer $f\ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k\ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q\le k\cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup [\frac{1}{f},1]$, for any constant integer $f\ge 2$.

19 pages, a short version of this paper appears in the proceedings of ISAAC 2026