Partial resampling to approximate covering integer programs. Issue 1 (27th September 2020)

• Record Type: Journal Article
• Authors: Chen, Antares; Harris, David G.; Srinivasan, Aravind
• Is Part Of: Random structures & algorithms. Volume 58:Issue 1(2021)
• Page Start: 68
• Page End: 93
• Publication Date: 2020-09-27
• Subjects: approximation algorithms -- integer program -- randomized rounding -- set cover; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20964
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We consider column‐sparse covering integer programs, a generalization of set cover. We develop a new rounding scheme based on the partial resampling variant of the Lovász Local Lemma developed by Harris and Srinivasan. This achieves an approximation ratio of 1 + ln ( Δ 1 + 1 ) a min + O ( log ( 1 + log ( Δ 1 + 1 ) a min ) ), where a min is the minimum covering constraint and Δ 1 is the maximum ℓ 1 ‐norm of any column of the covering matrix A (whose entries are scaled to lie in [0, 1]). With additional constraints on the variable sizes, we get an approximation ratio of ln Δ 0 + O ( log log Δ 0 ) (where Δ 0 is the maximum number of nonzero entries in any column of A ). These results improve asymptotically over results of Srinivasan and results of Kolliopoulos and Young. We show nearly‐matching lower bounds. We also show that the rounding process leads to negative correlation among the variables.