In a column-restricted covering integer program (CCIP), all the non-zero entries of any column of the constraint matrix are equal. Such programs capture capacitated versions of covering problems. In this paper, we study the approximability of CCIPs, in particular, their relation to the integrality gaps of the underlying 0,1-CIP. If the underlying 0,1-CIP has an integrality gap O(γ), and assuming that the integrality gap of the priority version of the 0,1-CIP is O(ω), we give a factor O(γ+ω) approximation algorithm for the CCIP. Priority versions of 0,1-CIPs (PCIPs) naturally capture quality of service type constraints in a covering problem. We investigate priority versions of the line (PLC) and the (rooted) tree cover (PTC) problems. Apart from being natural objects to study, these problems fall in a class of fundamental geometric covering problems. We bound the integrality of certain classes of this PCIP by a constant. Algorithmically, we give a polytime exact algorithm for PLC, show that the PTC problem is APX-hard, and give a factor 2-approximation algorithm for it.
Given matrices A and B and vectors a, b, c and d, all with non-negative entries, we consider the problem of computing min c^Tx:[email protected]?Z"+^n,Ax>=a,Bx==a) and multiplicity constraints (x= In 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(log m) 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(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 multiplicity constraints by a multiplicative O(1) factor.