How to Play Unique Games Using Embeddings

Berkeley, California October 21-October 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.36

47th Annual IEEE Symposium on Foundat ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Eden Chlamtac Articles by Konstantin Makarychev Articles by Yury Makarychev

	ASCII Text	x
	Eden Chlamtac, Konstantin Makarychev, Yury Makarychev, "How to Play Unique Games Using Embeddings," Foundations of Computer Science, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.