Moses Charikar
Konstantin Makarychev
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(√ε) fraction of all constraints. The best previously known result, due to Zwick, was 1 − O(ε1/3).
The second algorithm finds a ck/2k 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/(2k 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.
- ]]Agarwal, A., Charikar, M., Makarychev, K., and Makarychev, Y. 2005. O(&sqrt; log n) approximation algorithms for MIN Uncut, MIN 2CNF deletion, and directed cut problems. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York, 573--581. Google Scholar
Digital Library
- ]]Austrin, P. 2007a. Balanced MAX 2-SAT might not be the hardest. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing. ACM, New York, 189--197. Google ScholarDigital Library
- ]]Austrin, P. 2007b. Towards sharp inapproximability for any 2-CSP. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, 307--317. Google ScholarDigital Library
- ]]Austrin, P., and Mossel, E. 2008. Approximation resistant predicates from pairwise independence. In Proceedings of the IEEE 23rd Annual Conference on Computational Complexity. IEEE Computer Society, Los Alamitos, 249--258. Google ScholarDigital Library
- ]]Azar, Y., Motwani, R., and Naor, J. 1998. Approximating probability distributions using small sample spaces. Combinatorica 18, 2, 151--171.Google ScholarCross Ref
- ]]Charikar, M., and Wirth, A. 2004. Maximizing quadratic programs: Extending Grothendieck's inequality. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, 54--60. Google ScholarDigital Library
- ]]Feige, U., and Goemans, M. X. 1995. Approximating the value of two prover proof systems, with applications to MAX-2SAT and MAX DICUT. In Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems, 182--189. Google ScholarDigital Library
- ]]Goemans, M. X., and Williamson, D. P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semi-definite programming. J. ACM 42, 6, 1115--1145. Google ScholarDigital Library
- ]]Guruswami, V., and Raghavendra, P. 2008. Constraint satisfaction over a non-boolean domain: Approximation algorithms and unique-games hardness. In Proceedings of APPROX-RANDOM. 77--90. Google ScholarDigital Library
- ]]Hast, G. 2005. Approximating MAX kCSP—Out-performing a random assignment with almost a linear factor. In Proceedings of ICALP, 956--968. Google ScholarDigital Library
- ]]Håstad, J. 2001. Some optimal inapproximability results. J. ACM 48, 4, 798--859. Google ScholarDigital Library
- ]]Khot, S. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. ACM, New York, 767--775. Google ScholarDigital Library
- ]]Khot, S., Kindler, G., Mossel, E., and O'Donnell, R. 2007. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? SIAM J. Comput. 37, 1, 319--357. Google ScholarDigital Library
- ]]Lewin, M., Livnat, D., and Zwick, U. 2002. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization. Springer-Verlag, 67--82. Google ScholarDigital Library
- ]]Matuura, S. and Matsui, T. 2003. New approximation algorithms for MAX 2SAT and MAX DICUT. J. Oper. Res. Soc. Japan 46, 178--188.Google ScholarCross Ref
- ]]Nesterov, Y. 1997. Quality of semi-definite relaxation for nonconvex quadratic optimization. CORE Discussion Paper 9719.Google Scholar
- ]]Raghavendra, P. 2008. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM, New York, 245--254. Google ScholarDigital Library
- ]]Rietz, R. E. 1974. A proof of the Grothendieck inequality. Israel J. Math 19, 3, 271--276.Google ScholarCross Ref
- ]]Samorodnitsky, A., and Trevisan, L. 2006. Gowers uniformity, influence of variables, and PCPs. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. ACM, New York, 11--20. Google ScholarDigital Library
- ]]Trevisan, L. 1998. Parallel approximation algorithms by positive linear programming. Algorithmica 21, 1, 72--88.Google ScholarCross Ref
- ]]Zwick, U. 1998. Finding almost-satisfying assignments. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 551--560. Google ScholarDigital Library
- ]]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.Google Scholar
Index Terms
- Near-optimal algorithms for maximum constraint satisfaction problems
Recommendations
Near-optimal algorithms for maximum constraint satisfaction problems
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithmsIn this paper we present 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(√...
Fast SDP algorithms for constraint satisfaction problems
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsThe class of constraint satisfactions problems (CSPs) captures many fundamental combinatorial optimization problems such as Max Cut, Max q-Cut, Unique Games, and Max k-Sat. Recently, Raghavendra (STOC'08) identified a simple semidefinite programming ...
Comments