*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Abstract:
We give a subexponential-time approximation algorithm for the Unique > Games > problem: Given a Unique Games instance with optimal value 1-epsilon > and alphabet size k, our algorithm finds in time exp(k*n^beta) a > solution of value 1-sqrt(epsilon/beta^3). Here, beta>0 is a parameter > of the algorithm that can be chosen arbitrarily small. > > We also obtain subexponential algorithms with similar approximation > guarantees for Small-Set Expansion and Multi Cut. For Max Cut, > Sparsest Cut and Vertex Cover, our techniques lead to subexponential > algorithms with improved approximation guarantees on interesting subclasses of instances. > > Khot's Unique Games Conjecture (UGC) states that it is NP-hard to > achieve approximation guarantees such as ours for 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 > 3-SAT, Label Cover and more, that are believed not to have > subexponential algorithms achieving a non-trivial approximation guarantee. > > The main component in our algorithms is a new kind of graph > decomposition that may have other applications: We show that every > graph with n vertices can be efficiently partitioned into disjoint > induced subgraphs, each with at most n^beta eigenvalues above 1-eta, > such that at most a > sqrt(epsilon/beta^3) fraction of the edges of the graph does not > respect the partition. > > Joint work with Sanjeev Arora and Boaz Barak.
