loading...
Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations
Providence, Rhode Island October 21-October 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.7248th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We introduce a framework for studying semidefinite programming (SDP) relaxations based on the Lasserre hierarchy in the context of approximation algorithms for combinatorial problems. As an application of our approach, we give improved approximation algorithms for two problems. We show that for some fixed constant \varepsilon \le 0, given a 3- uniform hypergraph containing an independent set of size (\frac{1} {2} - \varepsilon )n, we can find an independent set of size \Omega (n^\varepsilon ). This improves upon the result of Krivelevich, Nathaniel and Sudakov, who gave an algorithm finding an independent set of size \Omega (n^{6\gamma - 3} ) for hypergraphs with an independent set of size \gamma n (but no guarantee for \gamma \leqslant \frac{1} {2}. We also give an algorithm which finds an {\rm O}(n^{0.2072} )-coloring given a 3-colorable graph, improving upon the work of Arora, Chlamtac and Charikar. Our approach stands in contrast to a long series of inapproximability results in the Lov?asz Schrijver linear programming (LP) and SDP hierarchies for other problems.
Citation:
Eden Chlamtac, "Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations," focs, pp.691-701, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.