Approximating Unique Games

The UNIQUE GAMES problem is the following: we are given a graph G = (V, E), with each edge e = (u, v) having a weight we and a permutation pi(uv) on [k]. The objective is to find a labeling of each vertex u with a label f(u) is an element of [k] to minimize the weight of unsatisfied edges-where an edge (u, v) is satisfied if f(v) = pi(uv)(f(u)). The Unique Games Conjecture of Khot [8] essentially says that for each epsilon > 0, there is a k such that it is NP-hard to distinguish instances of Unique games with (1-epsilon) satisfiable edges from those with only epsilon satisfiable edges. Several hardness results have recently been proved based on this assumption, including optimal ones for Max-Cut, Vertex-Cover and other problems, making it an important challenge to prove or refute the conjecture. In this paper, we give an O(log n)-approximation algorithm for the problem of minimizing the number of unsatisfied edges in any Unique game. Previous results of Khot [8] and Trevisan [12] imply that if the optimal solution has OPT = epsilon m unsatisfied edges, semidefinite relaxations of the problem could give labelings with min{k(2)epsilon(1/5), (epsilon logn)(1/2)}m unsatisfied edges. In this paper we show how to round a LP relaxation to get an O(log n)-approximation to the problem; i.e., to find a labeling with only O(epsilon mlogn) = O(OPT log n) unsatisfied edges.