Algorithms to approximate column-sparse packing problems

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

doi:10.1137/1.9781611975031.22

Algorithms to approximate column-sparse packing problems

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language	English (US)
Title of host publication	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Editors	Artur Czumaj
Publisher	Association for Computing Machinery
Pages	311-330
Number of pages	20
ISBN (Electronic)	9781611975031
DOIs	https://doi.org/10.1137/1.9781611975031.22
State	Published - 2018
Externally published	Yes
Event	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference	29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Country/Territory	United States
City	New Orleans
Period	1/7/18 → 1/10/18

All Science Journal Classification (ASJC) codes

Software
General Mathematics

Access to Document

10.1137/1.9781611975031.22

Cite this

Brubach, B., Sankararaman, K. A., Srinivasan, A., & Xu, P. (2018). Algorithms to approximate column-sparse packing problems. In A. Czumaj (Ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 (pp. 311-330). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.22

@inproceedings{dd8be8437bf34411889c156c649b15c4,

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 F{\"u}redi, Kahn and Seymour on hypergraph matching (Combinatorica, 1993).",

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

year = "2018",

doi = "10.1137/1.9781611975031.22",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "311--330",

editor = "Artur Czumaj",

booktitle = "29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018",

}

Brubach, B, Sankararaman, KA, Srinivasan, A & Xu, P 2018, Algorithms to approximate column-sparse packing problems. in A Czumaj (ed.), 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 311-330, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, United States, 1/7/18. https://doi.org/10.1137/1.9781611975031.22

Algorithms to approximate column-sparse packing problems. / Brubach, Brian; Sankararaman, Karthik A.; Srinivasan, Aravind et al.
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. ed. / Artur Czumaj. Association for Computing Machinery, 2018. p. 311-330 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Algorithms to approximate column-sparse packing problems

AU - Brubach, Brian

AU - Sankararaman, Karthik A.

AU - Srinivasan, Aravind

AU - Xu, Pan

PY - 2018

Y1 - 2018

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

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

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

U2 - 10.1137/1.9781611975031.22

DO - 10.1137/1.9781611975031.22

M3 - Conference contribution

AN - SCOPUS:85045567380

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 311

EP - 330

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -

Algorithms to approximate column-sparse packing problems

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this