Algorithms to approximate column-sparse packing problems

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

doi:10.1145/3355400

Algorithms to approximate column-sparse packing problems

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

Research output: Contribution to journal › Article › peer-review

4 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 language	English (US)
Article number	10
Journal	ACM Transactions on Algorithms
Volume	16
Issue number	1
DOIs	https://doi.org/10.1145/3355400
State	Published - Nov 2019
Externally published	Yes

All Science Journal Classification (ASJC) codes

Mathematics (miscellaneous)

Keywords

Approximation algorithms
Packing programs
Randomized algorithms

Access to Document

10.1145/3355400

Cite this

@article{cd6dd58527924793bf8d07417dea4abf,

title = "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).",

keywords = "Approximation algorithms, Packing programs, Randomized algorithms",

author = "Brian Brubach and Sankararaman, {Karthik A.} and Aravind Srinivasan and Pan Xu",

year = "2019",

month = nov,

doi = "10.1145/3355400",

language = "English (US)",

volume = "16",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - Algorithms to approximate column-sparse packing problems

AU - Brubach, Brian

AU - Sankararaman, Karthik A.

AU - Srinivasan, Aravind

AU - Xu, Pan

PY - 2019/11

Y1 - 2019/11

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

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

KW - Approximation algorithms

KW - Packing programs

KW - Randomized algorithms

UR - http://www.scopus.com/inward/record.url?scp=85075640726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075640726&partnerID=8YFLogxK

U2 - 10.1145/3355400

DO - 10.1145/3355400

M3 - Article

AN - SCOPUS:85075640726

SN - 1549-6325

VL - 16

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 10

ER -

Algorithms to approximate column-sparse packing problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this