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.