{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:02:49Z","timestamp":1773478969686,"version":"3.50.1"},"reference-count":24,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":3742,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s1571-0661(04)80663-7","type":"journal-article","created":{"date-parts":[[2004,9,29]],"date-time":"2004-09-29T16:47:47Z","timestamp":1096476467000},"page":"190-203","source":"Crossref","is-referenced-by-count":24,"title":["Exact Algorithms for MAX-SAT"],"prefix":"10.1016","volume":"86","author":[{"given":"Hantao","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Haiou","family":"Shen","sequence":"additional","affiliation":[]},{"given":"Felip","family":"Many\u00e0","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB1","doi-asserted-by":"crossref","unstructured":"J. Alber, J. Gramm, R. Niedermeier, Faster exact algorithms for hard problems: A parameterized point of view. Preprint, submitted to Elsevier, August, 2000","DOI":"10.1016\/S0012-365X(00)00199-0"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB2","doi-asserted-by":"crossref","unstructured":"F.A. Aloul, A. Ramani, I.L. Markov, K.A. Sakallah, Generic ILP versus specialized 0-1 ILP: An update. Technical Report CSE-TR-461-02, University of Michigan, Ann Arbor, Michigan, Aug., 2002.","DOI":"10.1109\/ICCAD.2002.1167571"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB3","unstructured":"T. Alsinet, F. Many\u00e0, J. Planes, Improved branch and bound algorithms for Max-SAT. Proc. of 6th International Conference on the Theory and Applications of Satisfiability Testing, SAT2003, pages 408\u2013415."},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB4","unstructured":"T. Alsinet, F. Many\u00e0, J. Planes, Improved branch and bound algorithms for Max-2-SAT and weighted Max-2-SAT. Catalonian Conference on Artificial Intelligence, 2003."},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB5","series-title":"Approximation algorithms for NP-hard problems, Chapter 10","first-page":"399","article-title":"Hardness of approximation","author":"Arora","year":"1997"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB6","unstructured":"N. Bansal, V. Raman, Upper bounds for MaxSat: Further improved. In Aggarwal and Rangan (eds.): Proceedings of 10th Annual conference on Algorithms and Computation, ISSAC'99, volume 1741 of Lecture Notes in Computer Science, pages 247\u2013258, Springer-Verlag, 1999."},{"issue":"4","key":"10.1016\/S1571-0661(04)80663-7_NEWBIB7","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1009725216438","article-title":"A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems","volume":"2","author":"Borchers","year":"1999","journal-title":"Journal of Combinatorial Optimization"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB8","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1090\/dimacs\/026\/19","article-title":"A linear programming and rounding approach to Max 2-Sat","volume":"26","author":"Cheriyan","year":"1996","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB9","doi-asserted-by":"crossref","DOI":"10.1016\/S0304-3975(01)00174-8","article-title":"A deterministic (2\u20132\/(k+1))n algorithm for k-SAT based on local search","author":"Dantsin","year":"2002","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"3","author":"Davis","year":"1960","journal-title":"Journal of the Association for Computing Machinery 7"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB11","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theorem-proving","volume":"7","author":"Davis","year":"1962","journal-title":"Communications of the Association for Computing Machinery"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB12","unstructured":"J.W. Freeman, Improvements to propositional satisfiability search algorithms. Ph.D. Dissertation, Dept. of Computer Science, University of Pennsylvania, 1995."},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB13","unstructured":"J. Gramm, E.A. Hirsch, R. Niedermeier, P. Rossmanith: New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT. Preprint, submitted to Elsevier, May, 2001"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB14","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02241270","article-title":"Algorithms for the maximum satisfiability problem","volume":"44","author":"Hansen","year":"1990","journal-title":"Computing"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB15","doi-asserted-by":"crossref","unstructured":"E.A. Hirsch. A new algorithm for MAX-2-SAT. In Proceedings of 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, vol. 1770, Lecture Notes in Computer Science, pages 65\u201373. Springer-Verlag.","DOI":"10.1007\/3-540-46541-3_5"},{"issue":"4","key":"10.1016\/S1571-0661(04)80663-7_NEWBIB16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1023\/A:1006340920104","article-title":"New worst-case upper bounds for SAT","volume":"24","author":"Hirsch","year":"2000","journal-title":"Journal of Automated Reasoning"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01531077","article-title":"Solving propositional satisfiability problems","volume":"1","author":"Jeroslow","year":"1990","journal-title":"Annals of mathematics and Artificial Intelligence"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB18","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","article-title":"Parameterizing above guaranteed values: MaxSat and MaxCut","volume":"31","author":"Mahajan","year":"1999","journal-title":"Journal of Algorithms"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB19","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, Some prospects for efficient fixed parameter algorithms. In Proc. of the 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM'98), Springer, LNCS 1521, pages 168\u2013185, November, 1998.","DOI":"10.1007\/3-540-49477-4_12"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB20","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jagm.2000.1075","article-title":"New upper bounds for maximum satisfiability","volume":"36","author":"Niedermeier","year":"2000","journal-title":"Journal of Algorithms"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB21","unstructured":"I. Schiermeyer. Pure literal look ahead: An O(1,497n) 3-satisfiability algorithm. In Franco et al (eds.) Proceedings of Workshop on the Satisfiability Problem, Report No. 96\u2013230, Universit\u00e4t zu K\u00f6ln, pages 127\u2013136, Siena, April 1996."},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB22","doi-asserted-by":"crossref","unstructured":"H. Shen, H. Zhang, An empirical study of max-2-sat phase transitions, Proc. of LICS'03 Workshop on Typical Case Complexity and Phase Transitions, Ottawa, CA, June 2003.","DOI":"10.1016\/S1571-0653(04)00464-0"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB23","series-title":"Cliques, Coloring and Satisfiability, volume 26","first-page":"587","article-title":"Comparative studies of constraint satisfaction and Davis-Putnam algorithms for maximum satisfiability problems","author":"Wallace","year":"1996"},{"key":"10.1016\/S1571-0661(04)80663-7_NEWBIB24","doi-asserted-by":"crossref","unstructured":"H. Xu, R.A. Rutenbar, K. Sakallah, sub-SAT: A formulation for related boolean satisfiability with applications in routing. ISPD'02, April, 2002, San Diego, CA.","DOI":"10.1145\/505388.505432"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104806637?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104806637?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T11:42:44Z","timestamp":1682768564000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066104806637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S1571066104806637"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(04)80663-7","relation":{},"ISSN":["1571-0661"],"issn-type":[{"value":"1571-0661","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}