[Colloquium] Guest speaker

[Ponda Barnes]

TTI-C Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Yury Makarychev
Speaker's home page: http://www.cs.princeton.edu/~ymakaryc/
 
Date: Thursday, March 15, 2007
Location: TTI-C Conference room
Time: 10:00am
 
Title: Approximation Algorithms for Unique Games
 
 Abstract:
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 Makaryche
.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org.
For future TTI-C talks and events, please go to
http://ttic.uchicago.edu/cal/month.php
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070312/c8ca216d/attachment-0001.htm