Near-optimal algorithms for maximum constraint satisfaction problems

ABSTRACT

In this article, we present two approximation algorithms for the maximum constraint satisfaction problem with k variables in each constraint (MAX k-CSP).

Given a (1 − ϵ) satisfiable 2CSP our first algorithm finds an assignment of variables satisfying a 1 − O(&sqrt;ϵ) fraction of all constraints. The best previously known result, due to Zwick, was 1 − O(ϵ^1/3).

The second algorithm finds a ck/2^k approximation for the MAX k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which had an approximation guarantee of Ω(k/(2^k log k)).

Both results are optimal assuming the unique games conjecture and are based on rounding natural semidefinite programming relaxations. We also believe that our algorithms and their analysis are simpler than those previously known.

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: Per Austrin, Balanced max 2-sat might not be the hardest, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250818]
• 3: Per Austrin, Towards Sharp Inapproximability For Any 2-CSP, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.307-317, October 21-23, 2007 [doi>10.1109/FOCS.2007.73]
• 4: Per Austrin , Elchanan Mossel, Approximation Resistant Predicates from Pairwise Independence, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.249-258, June 22-26, 2008 [doi>10.1109/CCC.2008.20]
• 5: Azar, Y., Motwani, R., and Naor, J. 1998. Approximating probability distributions using small sample spaces. Combinatorica 18, 2, 151--171.
• 6: Moses Charikar , Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.54-60, October 17-19, 2004 [doi>10.1109/FOCS.2004.39]
• 7: Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.182, January 04-06, 1995
• 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: Venkatesan Guruswami , Prasad Raghavendra, Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness, Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, August 25-27, 2008, Boston, MA, USA [doi>10.1007/978-3-540-85363-3_7]
• 10: Hast, G. 2005. Approximating MAX kCSP—Out-performing a random assignment with almost a linear factor. In Proceedings of ICALP, 956--968.
• 11: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 12: 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]
• 13: Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
• 14: Michael Lewin , Dror Livnat , Uri Zwick, Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.67-82, May 27-29, 2002
• 15: Matuura, S. and Matsui, T. 2003. New approximation algorithms for MAX 2SAT and MAX DICUT. J. Oper. Res. Soc. Japan 46, 178--188.
• 16: Nesterov, Y. 1997. Quality of semi-definite relaxation for nonconvex quadratic optimization. CORE Discussion Paper 9719.
• 17: Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374414]
• 18: Rietz, R. E. 1974. A proof of the Grothendieck inequality. Israel J. Math 19, 3, 271--276.
• 19: Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
• 20: Trevisan, L. 1998. Parallel approximation algorithms by positive linear programming. Algorithmica 21, 1, 72--88.
• 21: Uri Zwick, Finding almost-satisfying assignments, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.551-560, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276869]
• 22: Zwick, U. 2000. Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans. www.cs.au.ac.il/~zwick/my-online-papers.html.

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
MAX 2CSP, MAX k-CSP, SDP