{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T01:11:04Z","timestamp":1772068264307,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540671411","type":"print"},{"value":"9783540465416","type":"electronic"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_5","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"65-73","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A New Algorithm for MAX-2-SAT"],"prefix":"10.1007","author":[{"given":"Edward A.","family":"Hirsch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"5_CR1","unstructured":"T. Asano, D. P. Williamson, Improved Approximation Algorithms for MAX SAT, To appear in Proc. of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000."},{"key":"5_CR2","unstructured":"N. Bansal, V. Raman, Upper Bounds for MaxSat: Further Improved, To appear in Proc. of ISAAC\u201999."},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theorem-proving procedure, Proc. 3rd Annual ACM Symposium on the Theory of Computing, 1971, pp. 151\u2013159.","DOI":"10.1145\/800157.805047"},{"key":"5_CR4","unstructured":"E. Dantsin, Tautology proof systems based on the splitting method, Leningrad Division of Steklov Institute of Mathematics (LOMI), PhD Dissertation, Leningrad, 1982 (in Russian)."},{"key":"5_CR5","unstructured":"E. Dantsin and L. O. Fuentes and V. Kreinovich, Less than 2n satisfiability algorithm extended to the case when almost all clauses are short, Computer Science Department, University of Texas at El Paso, UTEP-CS-91-5, 1991."},{"key":"5_CR6","unstructured":"E. Dantsin, M. Gavrilovich, E. A. Hirsch, B. Konev, Approximation algorithms for Max Sat: a better performance ratio at the cost of a longer running time, PDMI preprint 14\/1998, available from ftp:\/\/ftp.pdmi.ras.ru\/pub\/publicat\/preprint\/1998\/14-98.ps"},{"key":"5_CR7","unstructured":"E. Ya. Dantsin, V. Ya. Kreinovich, Exponential upper bounds for the satisfiability problem, Proc. of the IX USSR conf. on math. logic, Leningrad, 1988 (in Russian)."},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann, D. Loveland, A machine program for theorem-proving, Comm. ACM, vol. 5, 1962, pp. 394\u2013397.","journal-title":"Comm. ACM"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis, H. Putnam, A computing procedure for quantification theory, J. ACM, vol. 7, 1960, pp. 201\u2013215.","journal-title":"J. ACM"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"U. Feige, M. X. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, Proc. of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal inapproximability results, Proc. of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"5_CR12","unstructured":"E. A. Hirsch, Two new upper bounds for SAT, Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 521\u2013530."},{"key":"5_CR13","unstructured":"E. A. Hirsch, New Worst-Case Upper Bounds for SAT, To appear in the special issue SAT-2000 and in the Journal of Automated Reasoning, Kluwer Academic Publishers, 2000."},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"H. Karloff, U. Zwick, A 7\/8-approximation algorithm for MAX 3SAT?, In Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, pp. 406\u2013415, 1997.","DOI":"10.1109\/SFCS.1997.646129"},{"issue":"1\u20132","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"O. Kullmann, New methods for 3-SAT decision and worst-case analysis, Theoretical Computer Science 223(1\u20132), 1999, pp.1\u201371.","journal-title":"Theoretical Computer Science"},{"key":"5_CR16","unstructured":"O. Kullmann, H. Luckhardt, Deciding propositional tautologies: Algorithms and their complexity, Preprint, 1997, 82 pages; The electronic version can be obtained at http:\/\/www.cs.utoronto.ca\/~kullmann . A journal version, Algorithms for SAT\/TAUT decision based on various measures, is to appear in Information and Computation."},{"key":"5_CR17","unstructured":"M. Mahajan and V. Raman, Parametrizing above guaranteed values: MaxSat and MaxCut, Technical Report TR97-033, Electronic Colloquium on Computational Complexity, 1997. To appear in Journal of Algorithms."},{"key":"5_CR18","unstructured":"B. Monien, E. Speckenmeyer, 3-satisfiability is testable in O(1.62r) steps, Bericht Nr. 3\/1979, Reihe Theoretische Informatik, Universit\u00e4t-Gesamthochschule-Paderborn."},{"key":"5_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"B. Monien, E. Speckenmeyer, Solving satisfiability in less then 2n steps, Discrete Applied Mathematics, vol. 10, 1985, pp. 287\u2013295.","journal-title":"Discrete Applied Mathematics"},{"key":"5_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/3-540-48523-6_54","volume-title":"New upper bounds for MaxSat","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith. New upper bounds for MaxSat, Technical Report KAM-DIMATIA Series 98\u2013401, Charles University, Praha, Faculty of Mathematics and Physics, July 1998. Extended abstract appeared in Proc. of the 26th International Colloquium on Automata, Languages, and Programming, LNCS 1644, pp. 575\u2013584, 1999. A journal version is to appear in Journal of Algorithms."},{"key":"5_CR21","unstructured":"Ch. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994, 532 p."},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudlak, M. E. Saks, F. Zane, An Improved Exponential-time Algorithm for k-SAT, Proc. of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 628\u2013637.","DOI":"10.1109\/SFCS.1998.743513"},{"issue":"1","key":"5_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V. Raman","year":"1998","unstructured":"V. Raman, B. Ravikumar and S. Srinivasa Rao, A simplified NP-complete MAXSAT problem, Information Processing Letters 65(1), 1998, pp. 1\u20136.","journal-title":"Information Processing Letters"},{"key":"5_CR24","first-page":"77","volume":"3","author":"J. A. Robinson","year":"1968","unstructured":"J. A. Robinson, Generalized resolution principle, Machine Intelligence, vol. 3, 1968, pp. 77\u201394.","journal-title":"Machine Intelligence"},{"key":"5_CR25","unstructured":"U. Sch\u00f6ning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, Proc. of the 40th Annual Symposium on Foundations of Computer Science, 1999. To appear."},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1006\/jagm.1994.1045","volume":"17","author":"M. Yannakakis","year":"1994","unstructured":"M. Yannakakis, On the Approximation of Maximum Satisfiability, Journal of Algorithms 17, 1994, pp. 475\u2013502.","journal-title":"Journal of Algorithms"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T02:57:15Z","timestamp":1737341835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}