We consider positive covering integer programs, which generalize set cover and which have attracted a long line of research developing (randomized) approximation algorithms. Srinivasan (2006) gave a rounding algorithm based on the FKG inequality for systems which are "column-sparse." This algorithm may return an integer solution in which the variables get assigned large (integral) values; Kolliopoulos & Young (2005) modified this algorithm to limit the solution size, at the cost of a worse approximation ratio. We develop a new rounding scheme based on the Partial Resampling variant of the Lovasz Local Lemma developed by Harris & Srinivasan (2013). This achieves an approximation ratio of 1 + ln([EQUATION]), where  a  min  is the minimum covering constraint and Δ 1  is the maximum  e  1 -norm of any column of the covering matrix (whose entries are scaled to lie in [0, 1]); we also show nearly-matching inapproximability and integrality-gap lower bounds.   Our approach improves asymptotically, in several different ways, over known results. First, it replaces Δ 0 , the maximum number of nonzeroes in any column (from the result of Srinivasan) by Δ 1  which is always - and can be much - smaller than Δ 0 ; this is the first such result in this context. Second, our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations. We also significantly improve upon the upper-bounds of Kolliopoulos & Young when the integer variables are required to be within (1 + e) of some given upper-bounds, and show nearly-matching inapproximability.
['Antares Chen', 'David G. Harris', 'Aravind Srinivasan']
Partial resampling to approximate covering integer programs