TY - GEN
T1 - How to play unique games using embeddings
AU - Chlamtac, Eden
AU - Makarychev, Konstantin
AU - Makarychev, Yury
PY - 2006
Y1 - 2006
N2 - In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 - ε) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(ε√ log n log k) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.
AB - In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 - ε) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(ε√ log n log k) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.
UR - http://www.scopus.com/inward/record.url?scp=38749131224&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38749131224&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2006.36
DO - 10.1109/FOCS.2006.36
M3 - Conference contribution
AN - SCOPUS:38749131224
SN - 0769527205
SN - 9780769527208
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 687
EP - 696
BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006
Y2 - 21 October 2006 through 24 October 2006
ER -