loading...
Approximation Algorithms for Unique Games
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.2246th 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 
   
Luca Trevisan, U.C. Berkeley

We present a polynomial time algorithm based on semidefinite programming that, given a unique game of value 1 - O(1/ log n), satisfies a constant fraction of constraints, where n is the number of variables. For suficiently large alphabets, it improves an algorithm of Khot (STOC?02) that satisfies a constant fraction of constraints in unique games of value 1 - O(1/(k^{10} (\log k)^5 )), where k is the size of the alphabet. We also present a simpler algorithm for the special case of unique games with linear constraints.

Finally, we present a simple approximation algorithm for 2-to-1 games.

Citation:
Luca Trevisan, "Approximation Algorithms for Unique Games," focs, pp.197-205, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.