Algorithms to approximate column-sparse packing problems

Brian Brubach, Karthik A. Sankararaman, Aravind Srinivasan, Pan Xu

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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

Original languageEnglish (US)
Article number10
JournalACM Transactions on Algorithms
Volume16
Issue number1
DOIs
StatePublished - Nov 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Approximation algorithms
  • Packing programs
  • Randomized algorithms

Fingerprint

Dive into the research topics of 'Algorithms to approximate column-sparse packing problems'. Together they form a unique fingerprint.

Cite this