Volume 4 (2008) Article 5 pp. 111-128

Approximation Algorithms for Unique Games

by Luca Trevisan

Received: May 11, 2008
Published: October 10, 2008
DOI: 10.4086/toc.2008.v004a005

Download article from ToC site:
[PS (295K)]    [PS.GZ (85K)]    [PS.ZIP (85K)]
[PDF (243K)]    [DVI (147K)]   
Misc.:
[HTML Bibliography] [Bibliography Source] [BibTeX] 
[About the Author(s)]
Keywords: complexity theory, approximation algorithms, constraint satisfaction, unique games
Categories: complexity theory, algorithms, approximation algorithms, constraint satisfaction, unique games
ACM Classification: F.2.2
AMS Classification: 68Q17

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 γ, ε > 0 it is NP-hard to distinguish games of value smaller than γ from games of value larger than 1-ε. Several recent inapproximability results rely on Khot's conjecture.

Considering the case of sub-constant ε, 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.