Near-optimal algorithms for unique games
Authors:
Open Access
- 21 May 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 205-214
Abstract
Unique games are constraint satisfaction problems that can be viewed as a generalization of Max-Cut to a larger domain size. The Unique Games Conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. It has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. Thus, proving or refuting this conjecture is an important goal. We present significantly improved approximation algorithms for unique games. For instances with domain size k where the optimal solution satisfies 1-ε fraction of all constraints, our algorithms satisfy roughly k-ε/(2-ε) and 1- O(√εlog k) fraction of all constraints. Our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. Our results are near optimal if the Unique Games Conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.Keywords
This publication has 12 references indexed in Scilit:
- Approximation Algorithms for Unique Games2005
- Noise stability of functions with low in.uences invariance and optimality2005
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 12005
- On the Hardness of Approximating Multicut and Sparsest-Cut2005
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems2005
- Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?2004
- Vertex cover might be hard to approximate to within 2-ε2004
- On Systems of Linear Equations with Two Variables per EquationLecture Notes in Computer Science, 2004
- A New Way of Using Semidefinite Programming with Applications to Linear Equations mod pJournal of Algorithms, 2001
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995