Approximation Algorithms for Unique Games

Unique games are constraint satisfaction problems that can be viewed as a generalization of MAX CUT to a larger domain:

We are given a graph G = (V,E) on n vertices and a permutation P_uv on the set of labels {1,…,k} for every edge (u, v). Our goal is to assign a label X_u in {1,…, k} to each vertex u, so as to maximize the number of satisfied constraints P_uv (X_u) = X_v.

This problem has recently attracted a lot of attention since hardness of approximation for many problems, such as Sparsest Cut and Vertex Cover, was proved assuming the Unique Games Conjecture. Roughly speaking, this conjecture says that even if almost all constraints in a unique game are satisfiable it is NP-hard to satisfy a small constant fraction of constraints.
Unique games pose a great challenge for our existing techniques:
Typically, semidefinite programming (SDP) relaxations are well suited for optimization problems involving boolean variables (e.g. MAX CUT). But little is known about how to analyze SDP solutions for problems with larger domains.

We present three approximation algorithms for Unique Games that satisfy roughly k^-epsilon/2, 1 – O(sqrt{epsilon log k}) and 1 – epsilon * O(sqrt{log k log n}) fraction of all constraints if a (1-epsilon) fraction of all constraints is satisfiable.

This talk is based on joint papers with Moses Charikar, Eden Chlamtac, and Konstantin Makarychev.