Title: Approximating Covering Integer Programs with Multiset Constraints

In a covering integer program (CIP), we seek an n-vector x of nonnegative integers, which minimizes c^{T}x, subject to Ax >= b, where all entries of A,b,c are nonnegative. In their most general form, CIPs include also multiset constraints of the type x <= d, i.e., arbitrarily large integers are not acceptable in the solution. The multiset 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(log m) cost-approximation with respect to the optimum of the linear relaxation is valid for general CIPs, but multiset 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 multiset constraints by a multiplicative O(log m) 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(log m) times the LP optimum while violating the multiset constraints by a multiplicative O(1) factor.