{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:51Z","timestamp":1725856971668},"publisher-location":"Cham","reference-count":38,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319388502"},{"type":"electronic","value":"9783319388519"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-38851-9_17","type":"book-chapter","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:33:54Z","timestamp":1464708834000},"page":"246-261","source":"Crossref","is-referenced-by-count":6,"title":["An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Poloczek","sequence":"first","affiliation":[]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,6,1]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.3233\/SAT190104","volume":"9","author":"A Abrame","year":"2015","unstructured":"Abrame, A., Habet, D.: Ahmaxsat: Description and evaluation of a branch and bound Max-SAT solver. J. Satisfiability, Boolean Model. Comput. 9, 89\u2013128 (2015). www.lsis.org\/habetd\/Djamal_Habet\/MaxSAT.html . Accessed on 02 Feb 2016","journal-title":"J. Satisfiability, Boolean Model. Comput."},{"key":"17_CR2","unstructured":"Andres, B., Kaufmann, B., Matheis, O., Schaub, T.: Unsatisfiability-based optimization in clasp. In: ICLP 2012, pp. 211\u2013221 (2012)"},{"key":"17_CR3","unstructured":"Argelich, J., Li, C.M., Many\u00e0, F., Planes, J.: MAX-SAT 2014: Ninth Max-SAT evaluation. www.maxsat.udl.cat\/14\/ . Accessed on 12 Jan 2016"},{"key":"17_CR4","unstructured":"Argelich, J., Li, C.M., Many\u00e0, F., Planes, J.: MAX-SAT 2015: Tenth Max-SAT evaluation. www.maxsat.udl.cat\/15\/ . Accessed on 02 Feb 2016"},{"key":"17_CR5","unstructured":"Belov, A., Diepold, D., Heule, M.J., J\u00e4rvisalo, M.: Proc. of SAT COMPETITION 2014: Solver and Benchmark Descriptions (2014). http:\/\/satcompetition.org\/edacc\/sc14\/ . Accessed on 28 Jan 2016"},{"key":"17_CR6","unstructured":"Cai, S., Luo, C., Thornton, J., Su, K.: Tailoring local search for partial MaxSAT. In: AAAI, pp. 2623\u20132629 (2014). the code is available at http:\/\/lcs.ios.ac.cn\/caisw\/MaxSAT.html . Accessed on 25 Jan 2016"},{"key":"17_CR7","doi-asserted-by":"crossref","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. Comput. Syst. Sci. 58, 622\u2013640 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_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"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/978-3-319-23264-5_31","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"M Gebser","year":"2015","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., Romero, J., Schaub, T.: Progress in clasp Series 3. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds.) LPNMR 2015. LNCS, vol. 9345, pp. 368\u2013383. Springer, Heidelberg (2015)"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Multi-criteria optimization in answer set programming. In: ICLP, pp. 1\u201310 (2011)","DOI":"10.1007\/978-3-642-20895-9_7"},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Gu, J., Purdom, P.W., Franco, J., Wah, B.W.: Algorithms for the satisfiability (SAT) problem: A survey. In: Satisfiability Problem: Theory and Applications, pp. 19\u2013152 (1996)","DOI":"10.1090\/dimacs\/035\/02"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2015","year":"2015","unstructured":"Heule, M., Weaver, S. (eds.): SAT 2015. LNCS, vol. 9340. Springer, Heidelberg (2015)"},{"issue":"3","key":"17_CR13","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"17_CR14","first-page":"215","volume":"1","author":"DS Johnson","year":"1997","unstructured":"Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: A case study in local optimization. Local Search Comb. Optim. 1, 215\u2013310 (1997)","journal-title":"Local Search Comb. Optim."},{"key":"17_CR15","unstructured":"Kaufmann, B.: Personal communication"},{"key":"17_CR16","unstructured":"Kaufmann, B.: Clasp: A conflict-driven nogood learning answer set solver (version 3.1.3). http:\/\/www.cs.uni-potsdam.de\/clasp\/ . Accessed on 28 Jan 2016"},{"key":"17_CR17","unstructured":"Kautz, H.: Walksat (version 51). www.cs.rochester.edu\/u\/kautz\/walksat\/ , see the source code for further references. Accessed on 27 Jan 2016"},{"issue":"1","key":"17_CR18","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","volume":"28","author":"S Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Sudan, M., Vazirani, U.V.: On syntactic versus computational views of approximability. SIAM J. Comput. 28(1), 164\u2013191 (1998)","journal-title":"SIAM J. Comput."},{"key":"17_CR19","unstructured":"Martins, R.: Personal communication"},{"key":"17_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1007\/978-3-319-10428-7_39","volume-title":"Principles and Practice of Constraint Programming","author":"R Martins","year":"2014","unstructured":"Martins, R., Joshi, S., Manquinho, V., Lynce, I.: Incremental cardinality constraints for MaxSAT. In: O\u2019Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 531\u2013548. Springer, Heidelberg (2014)"},{"key":"17_CR21","unstructured":"Martins, R., Manquinho, V., Lynce, I.: Open-WBO: An open source version of the MaxSAT solver WBO (version 1.3.0). http:\/\/sat.inesc-id.pt\/open-wbo\/index.html . Accessed on 25 Jan 2016"},{"key":"17_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"438","DOI":"10.1007\/978-3-319-09284-3_33","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2014","author":"R Martins","year":"2014","unstructured":"Martins, R., Manquinho, V., Lynce, I.: Open-WBO: a modular MaxSAT solver. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 438\u2013445. Springer, Heidelberg (2014)"},{"key":"17_CR23","unstructured":"Mastrolilli, M., Gambardella, L.M.: MAX-2-SAT: How good is Tabu Search in the worst-case? In: AAAI, pp. 173\u2013178 (2004)"},{"key":"17_CR24","unstructured":"Miyazaki, S., Iwama, K., Kambayashi, Y.: Database queries as combinatorial optimization problems. In: CODAS, pp. 477\u2013483 (1996)"},{"issue":"4","key":"17_CR25","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1007\/s10601-013-9146-2","volume":"18","author":"A Morgado","year":"2013","unstructured":"Morgado, A., Heras, F., Liffiton, M.H., Planes, J., Marques-Silva, J.: Iterative and core-guided MaxSAT solving: A survey and assessment. Constraints 18(4), 478\u2013534 (2013)","journal-title":"Constraints"},{"key":"17_CR26","unstructured":"Narodytska, N., Bacchus, F.: EvaSolver. https:\/\/www.cse.unsw.edu.au\/ninan\/ . Accessed on 04 Jan 2016"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Narodytska, N., Bacchus, F.: Maximum satisfiability using core-guided MaxSAT resolution. In: AAAI 2014, pp. 2717\u20132723 (2014)","DOI":"10.1609\/aaai.v28i1.9124"},{"key":"17_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-642-14186-7_19","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2010","author":"D Pankratov","year":"2010","unstructured":"Pankratov, D., Borodin, A.: On the relative merits of simple local search methods for the MAX-SAT problem. In: Strichman, O., Szeider, S. (eds.) SAT 2010. LNCS, vol. 6175, pp. 223\u2013236. Springer, Heidelberg (2010)"},{"key":"17_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-23719-5_4","volume-title":"Algorithms \u2013 ESA 2011","author":"M Poloczek","year":"2011","unstructured":"Poloczek, M.: Bounds on greedy algorithms for MAX\u00a0SAT. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 37\u201348. Springer, Heidelberg (2011)"},{"key":"17_CR30","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":"17_CR31","unstructured":"Poloczek, M., Schnitger, G., Williamson, D.P., van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: Simple algorithms and inapproximability bounds, In Submission"},{"key":"17_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1007\/978-3-642-54423-1_52","volume-title":"LATIN 2014: Theoretical Informatics","author":"M Poloczek","year":"2014","unstructured":"Poloczek, M., Williamson, D.P., van Zuylen, A.: On some recent approximation algorithms for MAX SAT. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 598\u2013609. Springer, Heidelberg (2014)"},{"key":"17_CR33","doi-asserted-by":"crossref","unstructured":"Selman, B., Kautz, H.A., Cohen, B.: Local search strategies for satisfiability testing. In: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, pp. 521\u2013532 (1993)","DOI":"10.1090\/dimacs\/026\/25"},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"Spears, W.M.: Simulated annealing for hard satisfiability problems. In: Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge, pp. 533\u2013558 (1993)","DOI":"10.1090\/dimacs\/026\/26"},{"issue":"10","key":"17_CR35","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"DA Spielman","year":"2009","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"17_CR36","unstructured":"Williamson, D.P.: Lecture notes in approximation algorithms, Fall 1998. IBM Research Report RC 21409, IBM Research (1999)"},{"key":"17_CR37","unstructured":"Zhang, Y., Zha, H., Chu, C.H., Ji, X.: Protein interaction interference as a Max-Sat problem. In: Proceedings of the IEEE CVPR 2005 Workshop on Computer Vision Methods for Bioinformatics (2005)"},{"key":"17_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-642-29116-6_16","volume-title":"Approximation and Online Algorithms","author":"A Zuylen van","year":"2012","unstructured":"van Zuylen, A.: Simpler 3\/4-approximation algorithms for MAX SAT. In: Solis-Oba, R., Persiano, G. (eds.) WAOA 2011. LNCS, vol. 7164, pp. 188\u2013197. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-38851-9_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T21:55:57Z","timestamp":1656626157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-38851-9_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319388502","9783319388519"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-38851-9_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}