Published: October 10, 2008
Abstract: [Plain Text Version]
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}\cdot (\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.