On the Lovász Theta function for Independent Sets in Sparse Graphs
2015Vol. 2, pp. 193–200
Citations Over TimeTop 18% of 2015 papers
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.
Related Papers
- → Formal and Informal Hierarchy in Different Types of Organization(2011)303 cited
- Transformation From AKNS Hierarchy to Burgers Hierarchy(2009)
- → Comment on "A counterpart of the WKI soliton hierarchy associated with so(3,R)"(2014)
- → The Degree Quantity Marker Function of the ‘you’ Degree Structure(2021)