Skip to main content

Subexponential Algorithms for Unique Games and Related Problems

Author(s): Arora, Sanjeev; Barak, Boaz; Steurer, David

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr14g1t
Full metadata record
DC FieldValueLanguage
dc.contributor.authorArora, Sanjeev-
dc.contributor.authorBarak, Boaz-
dc.contributor.authorSteurer, David-
dc.date.accessioned2021-10-08T19:50:08Z-
dc.date.available2021-10-08T19:50:08Z-
dc.date.issued2015-11en_US
dc.identifier.citationArora, Sanjeev, Boaz Barak, and David Steurer. "Subexponential Algorithms for Unique Games and Related Problems." Journal of the ACM 62, no. 5 (2015): pp. 1-25. doi:10.1145/2775105en_US
dc.identifier.urihttps://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.479.8295&rep=rep1&type=pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr14g1t-
dc.description.abstractSubexponential time approximation algorithms are presented for the Unique Games and Small-Set Expansion problems. Specifically, for some absolute constant c, the following two algorithms are presented. (1) An exp(knϵ)-time algorithm that, given as input a k-alphabet unique game on n variables that has an assignment satisfying 1-ϵc fraction of its constraints, outputs an assignment satisfying 1-ϵ fraction of the constraints. (2) An exp(nϵ/δ)-time algorithm that, given as input an n-vertex regular graph that has a set S of δn vertices with edge expansion at most ϵc, outputs a set S' of at most δ n vertices with edge expansion at most ϵ. subexponential algorithm is also presented with improved approximation to Max Cut, Sparsest Cut, and Vertex Cover on some interesting subclasses of instances. These instances are graphs with low threshold rank, an interesting new graph parameter highlighted by this work. Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While the results here stop short of refuting the UGC, they do suggest that Unique Games are significantly easier than NP-hard problems such as Max 3-Sat, Max 3-Lin, Label Cover, and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio. Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown 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 ϵ. The subexponential algorithm combines this decomposition with previous algorithms for Unique Games on graphs with few large eigenvalues [Kolla and Tulsiani 2007; Kolla 2010].en_US
dc.format.extent1 - 25en_US
dc.language.isoen_USen_US
dc.relation.ispartofJournal of the ACMen_US
dc.rightsAuthor's manuscripten_US
dc.titleSubexponential Algorithms for Unique Games and Related Problemsen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1145/2775105-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
Subexponential.pdf255.04 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.