  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\'{a}sz Local Lemma developed by Harris & Srinivasan (2019).
  This achieves an approximation ratio of $1 + \frac{\ln
(\Delta_1+1)}{a_{\min}} + O\Big( \log(1 + \sqrt{ \frac{\log
(\Delta_1+1)}{a_{\min}}} \Big)$, where $a_{\min}$ is the minimum covering
constraint and $\Delta_1$ is the maximum $\ell_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 \Delta_0 + O(\log \log \Delta_0)$ (where $\Delta_0$ 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.

Data Structures and Algorithms;Discrete Mathematics