How to Play Unique Games Using Embeddings
Eden Chlamtáč, Konstantin Makarychev, Yury Makarychev · 2006
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 - epsiv) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(epsiv radic(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