Partial resampling to approximate covering integer programs

We consider column-sparse covering integer programs, a generalization of set cover, which have a long line of research of (randomized) approximation algorithms. We develop a new rounding scheme based on the Partial Resampling variant of the Lov'asz Local Lemma developed by Harris & Srinivasan (2019). This achieves an approximation ratio of 1 + fracln (Delta1+1)amin + OBig( log(1 + √ fraclog (Delta1+1)amin Big), where amin is the minimum covering constraint and Delta1 is the maximum ℓ1-norm of any column of the covering matrix (whose entries are scaled to lie in [0,1]). When there are additional constraints on the variable sizes, we show an approximation ratio of ln Delta0 + O(log log Delta0) (where Delta0 is the maximum number of non-zero entries in any column of the covering matrix). These results improve asymptotically, in several different ways, over results of Srinivasan (2006) and Kolliopoulos & Young (2005). We show nearly-matching inapproximability and integrality-gap lower bounds. We also show that the rounding process leads to negative correlation among the variables, which allows us to handle multi-criteria programs.