Partial resampling to approximate covering integer programs†

Autor: Antares Chen, David G. Harris, Aravind Srinivasan
Rok vydání: 2020
Předmět:
Zdroj: Random Structures & Algorithms. 58:68-93
ISSN: 1098-2418
1042-9832
DOI: 10.1002/rsa.20964
Popis: We consider positive covering integer programs, which generalize set cover and which have attracted a long line of research developing (randomized) approximation algorithms. Srinivasan (2006) gave a rounding algorithm based on the FKG inequality for systems which are "column-sparse." This algorithm may return an integer solution in which the variables get assigned large (integral) values; Kolliopoulos & Young (2005) modified this algorithm to limit the solution size, at the cost of a worse approximation ratio. We develop a new rounding scheme based on the Partial Resampling variant of the Lovasz Local Lemma developed by Harris & Srinivasan (2013). This achieves an approximation ratio of 1 + ln([EQUATION]), where amin is the minimum covering constraint and Δ1 is the maximum e1-norm of any column of the covering matrix (whose entries are scaled to lie in [0, 1]); we also show nearly-matching inapproximability and integrality-gap lower bounds.Our approach improves asymptotically, in several different ways, over known results. First, it replaces Δ0, the maximum number of nonzeroes in any column (from the result of Srinivasan) by Δ1 which is always - and can be much - smaller than Δ0; this is the first such result in this context. Second, our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations. We also significantly improve upon the upper-bounds of Kolliopoulos & Young when the integer variables are required to be within (1 + e) of some given upper-bounds, and show nearly-matching inapproximability.
Databáze: OpenAIRE
Externí odkaz: