Name
Abstract | ||
|---|---|---|
We give a sub exponential time approximation algorithm for the \textsc{Unique Games} problem. The algorithms run in time that is exponential in an arbitrarily small polynomial of the input size, $n^{\epsilon}$. The approximation guarantee depends on~$\epsilon$, but not on the alphabet size or the number of variables. We also obtain a sub exponential algorithms with improved approximations for \textsc{Small-Set Expansion} and \textsc{Multicut}. For \textsc{Max Cut}, \textsc{Sparsest Cut}, and \textsc{Vertex Cover}, we give sub exponential 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 \textsc{Unique Games}. While our results stop short of refuting the UGC, they do suggest that \textsc{Unique Games} is significantly easier than NP-hard problems such as \textsc{Max 3Sat}, \textsc{Max 3Lin}, \textsc{Label Cover} and more, that are believed not to have a sub exponential 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 $\epsilon0$ and every regular $n$-vertex graph~$G$, by changing at most $\epsilon$ 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^{\epsilon}$ eigenvalues larger than $1-\eta$, where $\eta$ depends polynomially on $\epsilon$. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/2775105 | Journal of the ACM (JACM) |
Keywords | Field | DocType |
Approximation Algorithms,Unique Games,Subexponential Algorithms,Spectral Methods,Eigenvalues,Graph Decompositions,Constraint Satisfaction Problems | Adjacency matrix,Graph theory,Approximation algorithm,Discrete mathematics,Combinatorics,Disjoint sets,Polynomial,Unique games conjecture,Algorithm,Vertex cover,Maximum cut,Mathematics | Conference |
Volume | Issue | ISSN |
62 | 5 | 0004-5411 |
ISBN | Citations | PageRank |
978-1-4244-8525-3 | 31 | 1.17 |
References | Authors | |
44 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjeev Arora | 1 | 4508 | 379.31 |
| Boaz Barak | 2 | 2563 | 127.61 |
| David Steurer | 3 | 934 | 44.91 |