Approximating covering integer programs with multiplicity constraints

AbstractIn a covering integer program (CIP), we seek an n-vector x of nonnegative integers, which minimizes cT·x, subject to Ax⩾b, where all entries of A,b,c are nonnegative. In their most general form, CIPs include also multiplicity constraints of the type x⩽d, i.e., arbitrarily large integers are not acceptable in the solution. The multiplicity constraints incur a dichotomy with respect to approximation between (0,1)-CIPs whose matrix A contains only zeros and ones and the general case. Let m denote the number of rows of A. The well known O(logm) cost approximation with respect to the optimum of the linear relaxation is valid for general CIPs, but multiplicity constraints can be dealt with effectively only in the (0,1) case. In the general case, existing algorithms that match the integrality gap for the cost objective violate the multiplicity constraints by a multiplicative O(logm) factor. We make progress by defining column-restricted CIPs, a strict superclass of (0,1)-CIPs, and showing how to find for them integral solutions of cost O(logm) times the LP optimum while violating the multiplicity constraints by a multiplicative O(1) factor