In:
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), Vol. 16, No. 1 ( 2020-01-31), p. 1-32
Abstract:
Column-sparse packing problems arise in several contexts in both deterministic and stochastic discrete optimization. We present two unifying ideas, (non-uniform) attenuation and multiple-chance algorithms , to obtain improved approximation algorithms for some well-known families of such problems. As three main examples, we attain the integrality gap, up to lower-order terms, for known LP relaxations for k -column-sparse packing integer programs (Bansal et al., Theory of Computing , 2012) and stochastic k -set packing (Bansal et al., Algorithmica , 2012), and go “half the remaining distance” to optimal for a major integrality-gap conjecture of Füredi, Kahn, and Seymour on hypergraph matching ( Combinatorica , 1993).
Type of Medium:
Online Resource
ISSN:
1549-6325
,
1549-6333
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2020
detail.hit.zdb_id:
2198259-4
Permalink