{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:12Z","timestamp":1787340792400,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Suzann Wilson Matthews Summer Research Award"},{"DOI":"10.13039\/100003579","name":"American Friends of the Alexander von Humboldt Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100003579","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG SCHN 503\/6-1"],"award-info":[{"award-number":["DFG SCHN 503\/6-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1115256"],"award-info":[{"award-number":["CCF-1115256"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a $\\frac{3}{4}$-approximation in expectation. In contrast to previously known $\\frac{3}{4}$-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a $\\frac{3}{4}$-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within $\\frac{3}{4} + \\varepsilon$ (for any $\\varepsilon &gt; 0$). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio $\\frac{3}{4}$. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least $\\frac{3}{4} {OPT}_{LP}$, where ${OPT}_{LP}$ is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.<\/jats:p>","DOI":"10.1137\/15m1053369","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T12:56:25Z","timestamp":1497963385000},"page":"1029-1061","source":"Crossref","is-referenced-by-count":27,"title":["Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds"],"prefix":"10.1137","volume":"46","author":[{"given":"Matthias","family":"Poloczek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0028-y"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.014"},{"key":"atypb3","unstructured":"J. Argelich, C. M. Li, F. Many\u00e0, and J. Planes,\n                      MAX-SAT 2014: Ninth Max-SAT evaluation\n                      ,www.maxsat.udl.cat\/14\/, 2014, last accessed on 08\/19\/2015."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/070711670"},{"key":"atypb5","first-page":"27","author":"Avidor A.","year":"2005","journal-title":"Berlin"},{"key":"atypb6","first-page":"323","author":"Azar Y.","year":"2011","journal-title":"Berlin"},{"key":"atypb7","unstructured":"A. Belov, D. Diepold, M. J. H. Heule, and M. J\u00e4rvisalo,\n                      Proceedings of SAT Competition 2014: Solver and Benchmark Descriptions\n                      , University of Helsinki, 2014."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.033"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1036-3"},{"key":"atypb10","first-page":"649","author":"Buchbinder N.","year":"2012","journal-title":"Washington, DC"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/2811255"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1612"},{"key":"atypb14","first-page":"647","author":"Costello K. P.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9124-4"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.08.001"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192243516"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"H. J. Karloff and U. Zwick,\n                      A 7\/8-approximation algorithm for MAX 3SAT?\n                      , in Proceedings, 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 406-415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"atypb24","unstructured":"J. M. Kleinberg and \u00c9. Tardos,\n                      Algorithm Design\n                      , Addison-Wesley, Harlow, UK, 2006."},{"key":"atypb25","first-page":"67","author":"Lewin M.","year":"2002","journal-title":"Berlin"},{"key":"atypb26","unstructured":"S. Matuura and T. Matsui,\n                      0.935-Approximation Randomized Algorithm for MAX-2SAT and Its Derandomization\n                      , Technical Report METR 2001-03, Department of Mathematical Engineering and Physics, The University of Tokyo, Tokyo, Japan, 2001."},{"key":"atypb27","first-page":"37","author":"Poloczek M.","year":"2011","journal-title":"Berlin"},{"key":"atypb28","first-page":"656","author":"Poloczek M.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb29","first-page":"246","author":"Poloczek M.","year":"2016","journal-title":"Cham"},{"key":"atypb30","first-page":"598","author":"Poloczek M.","year":"2014","journal-title":"Berlin"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"A. van Zuylen,\n                      Simpler 3\/4-approximation algorithms for MAX SAT\n                      , in WAOA '11, Proceedings of the 9th International Conference on Approximation and Online Algorithms, Springer, Berlin, 2011, pp. 188-197.","DOI":"10.1007\/978-3-642-29116-6_16"},{"key":"atypb32","unstructured":"D. P. Williamson,\n                      Lecture Notes in Approximation Algorithms, Fall 1998\n                      , IBM Research Report RC 21409, IBM Research, 1999."},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"D. P. Williamson and D. B. Shmoys,\n                      The Design of Approximation Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511921735"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1045"},{"key":"atypb35","first-page":"420","author":"A","year":"1983","journal-title":"New York"},{"key":"atypb36","unstructured":"C. K. Yung,\n                      Inapproximation Result for Exact Max-2-SAT\n                      , unpublished manuscript, 2011."},{"key":"atypb37","first-page":"496","author":"Zwick U.","year":"2002","journal-title":"Philadelphia"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/15M1053369","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:48:14Z","timestamp":1787338094000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/15M1053369"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/15M1053369"],"URL":"https:\/\/doi.org\/10.1137\/15m1053369","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}