# Partial resampling to approximate covering integer programs

arXiv: https://arxiv.org/abs/1507.07402 · HTML: https://mlsanity.com/paper/1507.07402/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2015.

## Built on by (most cited first, 1 of 1)

- [Covering a Few Submodular Constraints and Applications](https://mlsanity.com/paper/2507.09879/) (2025)

## Abstract (arXiv)

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.