Title: Approximation Algorithms for Unique Games
Speaker: Konstantin Makarychev, Princeton University
Date: Wednesday, November 1, 2006 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size:
We are given a graph G, a set of labels [k] = {1,...,k}, and permutations pi_{uv} on the set [k] (for all edges (u,v)). Our goal is to find an assignment of labels to variables u) (for all vertices u) that maximizes the number of satisfied constraints v) = pi_{uv}(x(u)) (for edges (u,v)).
Given an instance where all constraints are satisfiable, it is easy to find such a satisfying assignment. Given an instance where 1-epsilon constraints are satisfiable, the Unique Games Conjecture of Khot says that it is hard to satisfy even delta fraction of the constraints (for k large enough). This conjecture has attracted a lot of recent attention since it has been shown to imply hardness of approximation results for several important problems that were difficult to approach by other means.
Another reason why unique games are interesting is that they are very challenging for existing SDP techniques: Typically SDP relaxations are well suited for optimization problems involving Boolean variables. But little is known about how to analyze SDP solutions when we have more than 2 states.
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 1 - epsilon fraction of all constraints is satisfiable.
This talk is based on joint works with Moses Charikar, Eden Chlamtac, and Yury Makarychev.