Theory of Computing
-------------------
Title     : Approximation Algorithms for Unique Games
Authors   : Luca Trevisan
Volume    : 4
Number    : 5
Pages     : 111-128
URL       : https://theoryofcomputing.org/articles/v004a005

Abstract
--------

A *unique game* is a type of  constraint satisfaction
problem with two variables per constraint. The *value*
of a unique game is the fraction of the constraints 
satisfied by an optimal solution.   Khot (STOC'02) 
conjectured that for arbitrarily small gamma, epsilon > 0
it is NP-hard to distinguish games of value smaller than
gamma  from games of value larger than  1-epsilon.  
Several recent inapproximability results rely on 
Khot's conjecture.

Considering the case of sub-constant  epsilon, Khot 
(STOC'02) analyzes an algorithm based on semidefinite 
programming that satisfies a constant fraction of the
constraints in unique games of value 
1-O(k^{-10} (\log k)^{-5}),  where  k  is the size of 
the domain of the variables.

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 
the constraints, where  n  is the number of variables. 
This is an improvement over Khot's algorithm if the 
domain is sufficiently large.

We also present a simpler algorithm for the special
case of unique games with  *linear*  constraints, and
a simple approximation algorithm for the more general
class of  2-to-1  games.