Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Near-optimal algorithms for maximum constraint satisfaction problems

Published: 04 July 2009 Publication History

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 − O1/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.

References

[1]
]]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.
[2]
]]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.
[3]
]]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.
[4]
]]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.
[5]
]]Azar, Y., Motwani, R., and Naor, J. 1998. Approximating probability distributions using small sample spaces. Combinatorica 18, 2, 151--171.
[6]
]]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.
[7]
]]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.
[8]
]]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.
[9]
]]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.
[10]
]]Hast, G. 2005. Approximating MAX kCSP—Out-performing a random assignment with almost a linear factor. In Proceedings of ICALP, 956--968.
[11]
]]Håstad, J. 2001. Some optimal inapproximability results. J. ACM 48, 4, 798--859.
[12]
]]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.
[13]
]]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.
[14]
]]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.
[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]
]]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.
[18]
]]Rietz, R. E. 1974. A proof of the Grothendieck inequality. Israel J. Math 19, 3, 271--276.
[19]
]]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.
[20]
]]Trevisan, L. 1998. Parallel approximation algorithms by positive linear programming. Algorithmica 21, 1, 72--88.
[21]
]]Zwick, U. 1998. Finding almost-satisfying assignments. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM, New York, 551--560.
[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.

Cited By

View all
  • (2023)SDPs and Robust Satisfiability of Promise CSPProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585180(609-622)Online publication date: 2-Jun-2023
  • (2021)The Quest for Strong Inapproximability Results with Perfect CompletenessACM Transactions on Algorithms10.1145/345966817:3(1-35)Online publication date: 15-Jul-2021
  • (2019)Robust Algorithms with Polynomial Loss for Near-Unanimity CSPsSIAM Journal on Computing10.1137/18M116393248:6(1763-1795)Online publication date: 26-Nov-2019
  • Show More Cited By

Index Terms

  1. Near-optimal algorithms for maximum constraint satisfaction problems

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Algorithms
    ACM Transactions on Algorithms  Volume 5, Issue 3
    July 2009
    222 pages
    ISSN:1549-6325
    EISSN:1549-6333
    DOI:10.1145/1541885
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 04 July 2009
    Accepted: 01 January 2009
    Revised: 01 December 2008
    Received: 01 February 2007
    Published in TALG Volume 5, Issue 3

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. MAX 2CSP
    2. MAX k-CSP
    3. SDP

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)18
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 13 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)SDPs and Robust Satisfiability of Promise CSPProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585180(609-622)Online publication date: 2-Jun-2023
    • (2021)The Quest for Strong Inapproximability Results with Perfect CompletenessACM Transactions on Algorithms10.1145/345966817:3(1-35)Online publication date: 15-Jul-2021
    • (2019)Robust Algorithms with Polynomial Loss for Near-Unanimity CSPsSIAM Journal on Computing10.1137/18M116393248:6(1763-1795)Online publication date: 26-Nov-2019
    • (2018)2 CSPs All Are Approximable Within a Constant Differential FactorCombinatorial Optimization10.1007/978-3-319-96151-4_33(389-401)Online publication date: 18-Jul-2018
    • (2017)Robust algorithms with polynomial loss for near-unanimity CSPsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039708(340-357)Online publication date: 16-Jan-2017
    • (2017)New checker for constraint network solutionsProceedings of the 2nd international Conference on Big Data, Cloud and Applications10.1145/3090354.3090408(1-6)Online publication date: 29-Mar-2017
    • (2017)The Power of Sherali--Adams Relaxations for General-Valued CSPsSIAM Journal on Computing10.1137/16M107924546:4(1241-1279)Online publication date: 20-Jul-2017
    • (2016)Approximation of non-boolean 2CSPProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884552(1705-1714)Online publication date: 10-Jan-2016
    • (2016)Candidate hard unique gameProceedings of the forty-eighth annual ACM symposium on Theory of Computing10.1145/2897518.2897531(63-76)Online publication date: 19-Jun-2016
    • (2016)Approximation Resistance from Pairwise-Independent SubgroupsJournal of the ACM10.1145/287305463:3(1-32)Online publication date: 12-Aug-2016
    • Show More Cited By

    View Options

    Get Access

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media