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

N. Bansal, Anupam Gupta, G. Guruganesh

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

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.
Original languageEnglish
Title of host publication47th Annual ACM Symposium on the Theory of Computing (STOC'15, Portland OR, USA, June 14-17, 2015)
EditorsR.A. Servedio, R. Rubinfeld
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages193-200
ISBN (Print)978-1-4503-3536-2
DOIs
Publication statusPublished - 2015
Event47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA - Portland, OR, United States
Duration: 14 Jun 201517 Jun 2015
http://acm-stoc.org/stoc2015/

Conference

Conference47th ACM Symposium on the Theory of Computing (STOC 2015), June 14-17, 2015, Portland, OR, USA
Abbreviated titleSTOC 2015
CountryUnited States
CityPortland, OR
Period14/06/1517/06/15
Internet address

Fingerprint

Dive into the research topics of 'On the Lovász theta function for independent sets in sparse graphs'. Together they form a unique fingerprint.

Cite this