Abstract
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 πuv on [k]. The objective is to find a labeling of each vertex u with a label fu ∈ [k] to minimize the weight of unsatisfied edges - where an edge (u, v) is satisfied if fv = πuv(fu). The Unique Games Conjecture of Khot [8] essentially says that for each ε > 0, there is a k such that it is NP-hard to distinguish instances of Unique games with (1-ε) satisfiable edges from those with only ε 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 = εm unsatisfied edges, semidefinite relaxations of the problem could give labelings with min{k2ε1/5, (ε log n)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(εm log n) = O(OPT log n) unsatisfied edges.
Original language | English (US) |
---|---|
Pages | 99-106 |
Number of pages | 8 |
DOIs | |
State | Published - 2006 |
Event | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States Duration: Jan 22 2006 → Jan 24 2006 |
Other
Other | Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Miami, FL |
Period | 1/22/06 → 1/24/06 |
ASJC Scopus subject areas
- Software
- General Mathematics