Algorithms to Approximate Column-Sparse Packing Problems

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).

Authors

• Brian Brubach
• Karthik Abinav Sankararaman
• Aravind Srinivasan
• Pan Xu 0001

Keywords

No keywords are indexed for this paper.