ProV Logo
0

Partial resampling to approximate coveri...
Chen, Antares...
Partial resampling to approximate covering integer programs by Chen, Antares ( Author )
N.A
27-07-2015
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ász Local Lemma developed by Harris & Srinivasan (2019). This achieves an approximation ratio of 1+ln(Δ1+1)amin+O(log(1+log(Δ1+1)amin−−−−−−−√), where amin is the minimum covering constraint and Δ1 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Δ0+O(loglogΔ0) (where Δ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.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
http://arxiv.org/abs/1507.07402
Share this eBook