Algorithmica

pp 1–18

# Simple Approximation Algorithms for Balanced MAX 2SAT

• Alice Paul
• Matthias Poloczek
• David P. Williamson
Article
Part of the following topical collections:
1. Special Issue on Theoretical Informatics

## Abstract

We study simple algorithms for the balanced MAX 2SAT problem, where we are given weighted clauses of length one and two with the property that for each variable x the total weight of clauses that x appears in equals the total weight of clauses for $$\overline{x}$$. We show that such instances have a simple structural property in that any optimal solution can satisfy at most the total weight of the clauses minus half the total weight of the unit clauses. Using this property and a novel analysis of the computation tree, we are able to show that a large class of greedy algorithms, including Johnson’s algorithm, gives a $$\frac{3}{4}$$-approximation algorithm for balanced MAX 2SAT; a similar statement is false for general MAX 2SAT instances. We further give a spectral 0.81-approximation algorithm for balanced MAX E2SAT instances (in which each clause has exactly 2 literals) by a reduction to a spectral algorithm of Trevisan for the maximum colored cut problem. We provide experimental results showing that this spectral algorithm performs well and is slightly better than Johnson’s algorithm and the Goemans–Williamson semidefinite programming algorithm on balanced MAX E2SAT instances.

### Keywords

Maximum satisfiability Approximation algorithm Greedy algorithm Spectral algorithm Balanced instances Priority algorithm

### References

1. 1.
Argelich, J., Li, C.M., Manyà, F., Planes, J.: MAX-SAT 2014: Ninth Max-SAT evaluation. www.maxsat.udl.cat/14/. Accessed on 13 June 2015
2. 2.
Austrin, P.: Towards sharp inapproximability for any 2-CSP. SIAM J. Comput. 39(6), 2430–2463 (2010)
3. 3.
Belov, A., Diepold, D., Heule, M.J., Järvisalo, M.: Proceedings of SAT Competition 2014: Solver and Benchmark Descriptions (2014)Google Scholar
4. 4.
Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44, 1384–1402 (2015)
5. 5.
Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large LP relaxations. J. ACM 63(4), 34:1–34:22 (2016)Google Scholar
6. 6.
Feige, U., Goemans, M.X.: Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In: Proceedings of the Third Israel Symposium on Theory of Computing and Systems (ISTCS), pp. 182–189 (1995)Google Scholar
7. 7.
Goemans, M.X., Williamson, D.P.: New 3/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656–666 (1994)
8. 8.
Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115–1145 (1995)
9. 9.
Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)
10. 10.
Khot, S., Kindler, G., Mossel, E., O’Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1), 319–357 (2007)
11. 11.
Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In: Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference (IPCO), pp. 67–82 (2002)Google Scholar
12. 12.
Matuura, S., Matsui, T.: 0.935-approximation randomized algorithm for MAX-2SAT and its derandomization. Technical Report METR 2001-03, Department of Mathematical Engineering and Physics, the University of Tokyo, Japan (2001)Google Scholar
13. 13.
Poloczek, M.: Bounds on greedy algorithms for MAX SAT. In: Proceedings of the 19th Annual European Symposium on Algorithms (ESA), pp. 37–48 (2011)Google Scholar
14. 14.
Poloczek, M.: Greedy algorithms for MAX SAT and maximum matching: Their power and limitations. Ph.D. thesis, Johann Wolfgang Goethe-Universität, Frankfurt am Main (2012)Google Scholar
15. 15.
Poloczek, M., Schnitger, G.: Randomized variants of Johnson’s algorithm for MAX SAT. In: Proceedings of the Twenty-Second Annual Symposium on Discrete Algorithms (SODA), pp. 656–663 (2011)Google Scholar
16. 16.
Poloczek, M., Schnitger, G., Williamson, D.P., van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: Simple algorithms and inapproximability bounds. SIAM J. Comput. (2017, accepted)Google Scholar
17. 17.
Poloczek, M., Williamson, D.P.: An experimental evaluation of fast approximation algorithms for the maximum satisfiability problem. In: Proceedings of the 15th International Symposium on Experimental Algorithms (SEA), pp. 246–261 (2016)Google Scholar
18. 18.
Poloczek, M., Williamson, D.P., van Zuylen, A.: On some recent approximation algorithms for MAX SAT. In: Proceedings of the 11th Latin American Theoretical INformatics Symposium (LATIN) (2014)Google Scholar
19. 19.
Soto, J.A.: Improved analysis of a Max-Cut algorithm based on spectral partitioning. SIAM J. Discrete Math. 29(1), 259–268 (2015)
20. 20.
Trevisan, L.: Max Cut and the smallest eigenvalue. SIAM J. Comput. 41(6), 1769–1786 (2012)
21. 21.
van Zuylen, A.: Simpler 3/4-approximation algorithms for MAX SAT. In: Proceedings of the 9th International Workshop on Approximation and Online Algorithms (WAOA), pp. 188–197 (2011)Google Scholar
22. 22.
Yannakakis, M.: On the approximation of maximum satisfiability. J. Algorithms 17(3), 475–502 (1994)

© Springer Science+Business Media New York 2017

## Authors and Affiliations

• Alice Paul
• 1
• Matthias Poloczek
• 1
• David P. Williamson
• 1
1. 1.School of Operations Research and Information EngineeringCornell UniversityIthacaUSA
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.951729416847229, "perplexity": 6375.947568909995}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2018-05/segments/1516084891277.94/warc/CC-MAIN-20180122093724-20180122113724-00718.warc.gz"}