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

Stefano Huber, Monaldo Mastrolilli

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 fo…