Downloads & Free Reading Options - Results

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. ©2007 Microsoft Corporation. All rights reserved.