TY - GEN

T1 - Subexponential algorithms for unique games and related problems

AU - Arora, Sanjeev

AU - Barak, Boaz

AU - Steurer, David

PY - 2010/12/1

Y1 - 2010/12/1

N2 - We give a subexponential time approximation algorithm for the Unique Games problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, nε. The approximation guarantee depends on ε, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the Unique Games. While our results stop short of refuting the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, LABEL COVER and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every ε > 0 and every regular n-vertex graph G, by changing at most ε fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most nε eigenvalues larger than 1 - η, where η depends polynomially on ε.

AB - We give a subexponential time approximation algorithm for the Unique Games problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, nε. The approximation guarantee depends on ε, but not on the alphabet size or the number of variables. We also obtain a subexponential algorithms with improved approximations for SMALL-SET EXPANSION and MULTICUT. For MAX CUT, SPARSEST CUT, and VERTEX COVER, we give subexponential algorithms with improved approximations on some interesting subclasses of instances. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for the Unique Games. While our results stop short of refuting the UGC, they do suggest that Unique Games is significantly easier than NP-hard problems such as MAX 3SAT, MAX 3LIN, LABEL COVER and more, that are believed not to have a subexponential algorithm achieving a non-trivial approximation ratio. The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every ε > 0 and every regular n-vertex graph G, by changing at most ε fraction of G's edges, one can break G into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most nε eigenvalues larger than 1 - η, where η depends polynomially on ε.

KW - Approximation algorithms

KW - Constraint satisfaction problems

KW - Eigenvalues

KW - Graph decompositions

KW - Spectral methods

KW - Subexponential algorithms

KW - Unique games

UR - http://www.scopus.com/inward/record.url?scp=78751539332&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78751539332&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2010.59

DO - 10.1109/FOCS.2010.59

M3 - Conference contribution

AN - SCOPUS:78751539332

SN - 9780769542447

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 563

EP - 572

BT - Proceedings - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

T2 - 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010

Y2 - 23 October 2010 through 26 October 2010

ER -