Algorithms to Approximate Column-Sparse Packing Problems

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 Furedi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).

Extended abstract appeared in SODA 2018. Full version in ACM Transactions of Algorithms

References in corpus (4)

• Constrained Submodular Maximization via a Non-symmetric Technique
• Non-negative submodular stochastic probing via stochastic contention resolution schemes
• Deterministic Discrepancy Minimization via the Multiplicative Weight Update Method
• Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

Cited by in corpus (1)

• Barter Exchange with Shared Item Valuations