Near-optimal algorithms for unique games

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.

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Gunnar Andersson , Lars Engebretsen , Johan Håstad, A new way of using semidefinite programming with applications to linear equations mod p, Journal of Algorithms, v.39 n.2, p.162-204, May 2001 [doi>10.1006/jagm.2000.1154]
• 3: Shuchi Chawla , Robert Krauthgamer , Ravi Kumar , Yuval Rabani , D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.144-153, June 11-15, 2005 [doi>10.1109/CCC.2005.20]
• 4: E. Chlamtac, K. Makarychev and Y. Makarychev. How to play any Unique Game. manuscript, February 2006.
• 5: I. Dinur, E. Mossel, and O. Regev. Conditional hardness for approximate coloring. ECCC Technical Report TR05-039, 2005.
• 6: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 7: U. Feige and D. Reichman. On systems of linear equations with two variables per equation. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization, vol. 3122 of Lecture Notes in Computer Science, pp. 117--127, 2004.
• 8: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 9: Anupam Gupta , Kunal Talwar, Approximating unique games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.99-106, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109569]
• 10: Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510017]
• 11: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O'Donnell, Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.146-154, October 17-19, 2004 [doi>10.1109/FOCS.2004.49]
• 12: S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? ECCC Report TR05-101, 2005.
• 13: S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. In Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 379--386, 2003.
• 14: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 15: Elchanan Mossel , Ryan O'Donnell , Krzysztof Oleszkiewicz, Noise stability of functions with low in.uences invariance and optimality, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.21-30, October 23-25, 2005 [doi>10.1109/SFCS.2005.53]
• 16: Z. Šidák. Rectangular Confidence Regions for the Means of Multivariate Normal Distributions. Journal of the American Statistical Association, vol. 62, no. 318, pp. 626--633, Jun. 1967.
• 17: Luca Trevisan, Approximation Algorithms for Unique Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.197-205, October 23-25, 2005 [doi>10.1109/SFCS.2005.22]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, constraint satisfaction problems, semidefinite programming, unique games