How to Play Unique Games Using Embeddings
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 687-696
Abstract
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 - epsiv) fraction of all constraints is satisfiable, the algorithm finds an assignment satisfying a 1 - O(epsiv radic(log n log k)) fraction of all constraints. To this end, we introduce new embedding techniques for rounding semidefinite relaxations of problems with large domain sizeKeywords
This publication has 6 references indexed in Scilit:
- Near-optimal algorithms for unique games2006
- Euclidean distortion and the sparsest cut2005
- Expander flows, geometric embeddings and graph partitioning2004
- On the power of unique 2-prover 1-round games2003
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Approximate max-flow min-(multi)cut theorems and their applications1993