loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
How to Play Unique Games Using Embeddings
Berkeley, California
October 21-October 24
ISBN: 0-7695-2720-5
ASCII Text
x 
 
Eden Chlamtac, Konstantin Makarychev, Yury Makarychev, "How to Play Unique Games Using Embeddings," Foundations of Computer Science, IEEE Annual Symposium on, pp. 687-696, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2006.36,
author = {Eden Chlamtac and Konstantin Makarychev and Yury Makarychev},
title = {How to Play Unique Games Using Embeddings},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2006},
issn = {0272-5428},
pages = {687-696},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.36},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - How to Play Unique Games Using Embeddings
SN - 0272-5428
SP687
EP696
A1 - Eden Chlamtac,
A1 - Konstantin Makarychev,
A1 - Yury Makarychev,
PY - 2006
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Eden Chlamtac, Princeton University, USA
Konstantin Makarychev, Princeton University, USA
Yury Makarychev, Princeton University, USA
In this paper we present a new approximation algorithm for Unique Games. For a Unique Game with n vertices and k states (labels), if a (1 - \varepsilon) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a

1 - O\left( {\varepsilon \sqrt {\log n\log k} } \right)

fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain size.

Citation:
Eden Chlamtac, Konstantin Makarychev, Yury Makarychev, "How to Play Unique Games Using Embeddings," focs, pp.687-696, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.