Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-041 | 11th March 2010 19:52

#### Improved Algorithms for Unique Games via Divide and Conquer

TR10-041
Authors: Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer
Publication: 11th March 2010 21:03
We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. The second algorithm runs in mildly exponential time, $e^{\alpha n}$, but makes no assumptions about the underlying constraint graph. As the completeness approaches $1$ (completeness $1-\epsilon$), the constant $\alpha$ in the running time rapidly approaches $0$ ($\alpha = exp(-\Omega(1/\epsilon))$.) The value of the solutions returned by these algorithms depend only on the completeness of the Unique Game and either the local conductance or the allowed running time respectively. In particular, the performance of these algorithms does not depend on the number of labels in the Unique Game.