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

N. Bansal, Anupam Gupta, G. Guruganesh

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

9 Citaten (Scopus)

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-2Engels
Titel47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)
RedacteurenR.A. Servedio, R. Rubinfeld
Plaats van productieNew York NY
UitgeverijAssociation for Computing Machinery, Inc
Pagina's193-200
ISBN van geprinte versie978-1-4503-3536-2
DOI's
StatusGepubliceerd - 2015
Evenement47th 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 201517 jun 2015
http://acm-stoc.org/stoc2015/

Congres

Congres47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA
Verkorte titelSTOC 2015
Land/RegioVerenigde Staten van Amerika
StadPortland, OR
Periode14/06/1517/06/15
Ander47th Annual ACM Symposium on the Theory of Computing
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'On the Lovász theta function for independent sets in sparse graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit