{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:50Z","timestamp":1759639070551},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_4","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"37-48","source":"Crossref","is-referenced-by-count":16,"title":["Bounds on Greedy Algorithms for MAX\u00a0SAT"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Poloczek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","first-page":"38","volume":"16","author":"M. Alekhnovich","year":"2009","unstructured":"Alekhnovich, M., Borodin, A., Buresh-Oppenheim, J., Impagliazzo, R., Magen, A.: Toward a model for backtracking and dynamic programming. Electronic Colloquium on Computational Complexity (ECCC)\u00a016, 38 (2009)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"26-28","key":"4_CR2","doi-asserted-by":"publisher","first-page":"2542","DOI":"10.1016\/j.tcs.2010.03.014","volume":"411","author":"S. Angelopoulos","year":"2010","unstructured":"Angelopoulos, S., Borodin, A.: Randomized priority algorithms. Theor. Comput. Sci.\u00a0411(26-28), 2542\u20132558 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/11671411_3","volume-title":"Approximation and Online Algorithms","author":"A. Avidor","year":"2006","unstructured":"Avidor, A., Berkovitch, I., Zwick, U.: Improved approximation algorithms for MAX\u00a0NAE-SAT and MAX\u00a0SAT. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol.\u00a03879, pp. 27\u201340. Springer, Heidelberg (2006)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Roth, R.: Submodular Max-SAT. In: ESA (2011)","DOI":"10.1007\/978-3-642-23719-5_28"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.tcs.2009.09.033","volume":"411","author":"A. Borodin","year":"2010","unstructured":"Borodin, A., Boyar, J., Larsen, K.S., Mirmohammadi, N.: Priority algorithms for graph optimization problems. Theor. Comput. Sci.\u00a0411(1), 239\u2013258 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"4_CR6","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s00453-003-1036-3","volume":"37","author":"A. Borodin","year":"2003","unstructured":"Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica\u00a037(4), 295\u2013326 (2003)","journal-title":"Algorithmica"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1006\/jcss.1998.1612","volume":"58","author":"J. Chen","year":"1999","unstructured":"Chen, J., Friesen, D.K., Zheng, H.: Tight bound on Johnson\u2019s algorithm for maximum satisfiability. J.\u00a0Comput. Syst. Sci.\u00a058(3), 622\u2013640 (1999)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Costello, K.P., Shapira, A., Tetali, P.: Randomized greedy: new variants of some classic approximation algorithms. In: SODA, pp. 647\u2013655 (2011)","DOI":"10.1137\/1.9781611973082.50"},{"issue":"3","key":"4_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-007-9124-4","volume":"54","author":"S. Davis","year":"2009","unstructured":"Davis, S., Impagliazzo, R.: Models of greedy algorithms for graph problems. Algorithmica\u00a054(3), 269\u2013317 (2009)","journal-title":"Algorithmica"},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"M.X. Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math.\u00a07(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"4_CR11","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci.\u00a09(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR12","unstructured":"Poloczek, M.: Bounds on greedy algorithms for MAX SAT, http:\/\/www.thi.cs.uni-frankfurt.de\/poloczek\/maxsatesa11.pdf"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Poloczek, M., Schnitger, G.: Randomized variants of Johnson\u2019s algorithm for MAX SAT. In: SODA, pp. 656\u2013663 (2011)","DOI":"10.1137\/1.9781611973082.51"},{"key":"4_CR14","unstructured":"van Zuylen, A.: Simpler 3\/4 approximation algorithms for MAX SAT (submitted)"},{"key":"4_CR15","first-page":"420","volume-title":"FOCS","author":"A.C.-C. Yao","year":"1983","unstructured":"Yao, A.C.-C.: Lower bounds by probabilistic arguments. In: FOCS, pp. 420\u2013428. IEEE, Los Alamitos (1983)"},{"key":"4_CR16","unstructured":"Yung, C.K.: Inapproximation result for exact Max-2-SAT (unpublished manuscript)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T12:07:55Z","timestamp":1560514075000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}