Approximating unique games

Anupam Gupta, Kunal Talwar

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
Pages99-106
Number of pages8
DOIs
StatePublished - 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityMiami, FL
Period1/22/061/24/06

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Approximating unique games'. Together they form a unique fingerprint.

Cite this