Title :
Subexponential Algorithms for Unique Games and Related Problems
Author :
Arora, Sanjeev ; Barak, Boaz ; Steurer, David
Author_Institution :
Comput. Sci. Dept, Princeton Univ., Princeton, NJ, USA
Abstract :
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 ε.
Keywords :
computational complexity; eigenvalues and eigenfunctions; graph theory; optimisation; polynomial approximation; stochastic games; NP-hard problems; Unique Games conjecture states; eigenvalues; graph decomposition; induced graph; max cut; multicut; nontrivial approximation ratio; polynomial; small-set expansion; sparsest cut; stochastic adjacency matrix; subexponential time approximation algorithm; vertex cover; Approximation algorithms; Approximation methods; Complexity theory; Eigenvalues and eigenfunctions; Games; Graph theory; Polynomials; Approximation Algorithms; Constraint Satisfaction Problems; Eigenvalues; Graph Decompositions; Spectral Methods; Subexponential Algorithms; Unique Games;
Conference_Titel :
Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on
Conference_Location :
Las Vegas, NV
Print_ISBN :
978-1-4244-8525-3
DOI :
10.1109/FOCS.2010.59