On the Lovász theta function for independent sets in sparse graphs

N. Bansal; Anupam Gupta; G. Guruganesh

doi:10.1145/2746539.2746607

On the Lovász theta function for independent sets in sparse graphs

N. Bansal, Anupam Gupta, G. Guruganesh

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

9 Citaten (Scopus)

4 Downloads (Pure)

Samenvatting

We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). This improves on the previous best result of O~(d/log d), and narrows the gap of this basic SDP to the integrality gap of O~(d/log2 d) recently shown for stronger SDPs, namely those obtained using poly log(d) levels of the SA+ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show how to obtain an algorithmic version of the above-mentioned SAplus-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of O~(d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

Originele taal-2	Engels
Titel	47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)
Redacteuren	R.A. Servedio, R. Rubinfeld
Plaats van productie	New York NY
Uitgeverij	Association for Computing Machinery, Inc
Pagina's	193-200
ISBN van geprinte versie	978-1-4503-3536-2
DOI's	https://doi.org/10.1145/2746539.2746607
Status	Gepubliceerd - 2015
Evenement	47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA - Portland, OR, Verenigde Staten van Amerika Duur: 14 jun. 2015 → 17 jun. 2015 http://acm-stoc.org/stoc2015/

Congres

Congres	47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA
Verkorte titel	STOC 2015
Land/Regio	Verenigde Staten van Amerika
Stad	Portland, OR
Periode	14/06/15 → 17/06/15
Ander	47th Annual ACM Symposium on the Theory of Computing
Internet adres	http://acm-stoc.org/stoc2015/

Toegang tot document

10.1145/2746539.2746607

Citeer dit

@inproceedings{fa76ff0db9ec4e0b8809a5f0a7cadaeb,

title = "On the Lov{\'a}sz theta function for independent sets in sparse graphs",

abstract = "We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). This improves on the previous best result of O~(d/log d), and narrows the gap of this basic SDP to the integrality gap of O~(d/log2 d) recently shown for stronger SDPs, namely those obtained using poly log(d) levels of the SA+ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show how to obtain an algorithmic version of the above-mentioned SAplus-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of O~(d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.",

author = "N. Bansal and Anupam Gupta and G. Guruganesh",

year = "2015",

doi = "10.1145/2746539.2746607",

language = "English",

isbn = "978-1-4503-3536-2",

pages = "193--200",

editor = "R.A. Servedio and R. Rubinfeld",

booktitle = "47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

note = "47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA, STOC 2015 ; Conference date: 14-06-2015 Through 17-06-2015",

url = "http://acm-stoc.org/stoc2015/",

}

Bansal, N, Gupta, A & Guruganesh, G 2015, On the Lovász theta function for independent sets in sparse graphs. in RA Servedio & R Rubinfeld (uitgave), 47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015). Association for Computing Machinery, Inc, New York NY, blz. 193-200, 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA, Portland, OR, Verenigde Staten van Amerika, 14/06/15. https://doi.org/10.1145/2746539.2746607

On the Lovász theta function for independent sets in sparse graphs. / Bansal, N.; Gupta, Anupam; Guruganesh, G.
47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015). uitgave / R.A. Servedio; R. Rubinfeld. New York NY: Association for Computing Machinery, Inc, 2015. blz. 193-200.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - On the Lovász theta function for independent sets in sparse graphs

AU - Bansal, N.

AU - Gupta, Anupam

AU - Guruganesh, G.

PY - 2015

Y1 - 2015

N2 - We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). This improves on the previous best result of O~(d/log d), and narrows the gap of this basic SDP to the integrality gap of O~(d/log2 d) recently shown for stronger SDPs, namely those obtained using poly log(d) levels of the SA+ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show how to obtain an algorithmic version of the above-mentioned SAplus-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of O~(d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

AB - We consider the maximum independent set problem on graphs with maximum degree d. We show that the integrality gap of the Lovasz Theta function-based SDP has an integrality gap of O~(d/log3/2 d). This improves on the previous best result of O~(d/log d), and narrows the gap of this basic SDP to the integrality gap of O~(d/log2 d) recently shown for stronger SDPs, namely those obtained using poly log(d) levels of the SA+ semidefinite hierarchy. The improvement comes from an improved Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show how to obtain an algorithmic version of the above-mentioned SAplus-based integrality gap result, via a coloring algorithm of Johansson. The resulting approximation guarantee of O~(d/log2 d) matches the best unique-games-based hardness result up to lower-order poly (log log d) factors.

U2 - 10.1145/2746539.2746607

DO - 10.1145/2746539.2746607

M3 - Conference contribution

SN - 978-1-4503-3536-2

SP - 193

EP - 200

BT - 47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)

A2 - Servedio, R.A.

A2 - Rubinfeld, R.

PB - Association for Computing Machinery, Inc

CY - New York NY

T2 - 47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA

Y2 - 14 June 2015 through 17 June 2015

ER -

On the Lovász theta function for independent sets in sparse graphs

Samenvatting

Congres

Toegang tot document

Vingerafdruk

Citeer dit