{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T04:10:35Z","timestamp":1734581435197,"version":"3.30.2"},"reference-count":20,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s1571-0653(04)00464-0","type":"journal-article","created":{"date-parts":[[2004,10,24]],"date-time":"2004-10-24T03:07:12Z","timestamp":1098587232000},"page":"80-92","source":"Crossref","is-referenced-by-count":6,"special_numbering":"C","title":["An Empirical Study of MAX-2-SAT Phase Transitions"],"prefix":"10.1016","volume":"16","author":[{"given":"Haiou","family":"Shen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hantao","family":"Zhag","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas and G. B. Sorkin, Optimal myopic algorithms for 3-SAT, 41st Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA 2001, pp. 590\u2013600.","DOI":"10.1109\/SFCS.2000.892327"},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB2","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-0653(04)00464-0_NEWBIB3","unstructured":"S. Arora, C. Lund. Hardness of approximation. In D. Hochbaum (ed.): Approximation algorithms for NP-hard problems, Chapter 10, pages 399\u2013446."},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB4","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":"no 3","key":"10.1016\/S1571-0653(04)00464-0_NEWBIB5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/rsa.1006","article-title":"The scaling window of the 2-SAT transition","volume":"18","author":"Bollobas","year":"2001","journal-title":"Random Structures and Algorithms"},{"issue":"4","key":"10.1016\/S1571-0653(04)00464-0_NEWBIB6","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-0653(04)00464-0_NEWBIB7","unstructured":"A. Z. Broder, A. M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX 1993, ACM Press, 1993, pp. 322\u2013330."},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB8","doi-asserted-by":"crossref","unstructured":"V. Chvatal, B. Reed, Mick gets some (the odds are on his side), 33th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, 1992. IEEE Comput. Soc. Press, 1992, pp. 620\u2013627.","DOI":"10.1109\/SFCS.1992.267789"},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB9","doi-asserted-by":"crossref","unstructured":"D. Coppersmith, D. Gamarnik, M. Hajiaghay, G. B. Sorkin. Random MAX SAT, random MAX CUT, and their phase transitions. Proceedings of Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 12\u201314, 2003, Baltimore, MD.","DOI":"10.1002\/rsa.20015"},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB10","doi-asserted-by":"crossref","unstructured":"E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Sch\u00f6ning. A deterministic (2\u20132\/(k+1))n algorithm for k\u2013SAT based on local search. Theoretical Computer Science> 2002.","DOI":"10.1016\/S0304-3975(01)00174-8"},{"issue":"no. 3","key":"10.1016\/S1571-0653(04)00464-0_NEWBIB11","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","article-title":"A threshold for unsatisfiability","volume":"53","author":"Goerdt","year":"1996","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB12","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-0653(04)00464-0_NEWBIB13","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-0653(04)00464-0_NEWBIB14","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-0653(04)00464-0_NEWBIB15","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"},{"issue":"no. 2","key":"10.1016\/S1571-0653(04)00464-0_NEWBIB16","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","article-title":"Bounding the unsatisfiability threshold of random 3-SAT","volume":"17","author":"Janson","year":"2000","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S1571-0653(04)00464-0_NEWBIB17","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-0653(04)00464-0_NEWBIB18","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-0653(04)00464-0_NEWBIB19","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-0653(04)00464-0_NEWBIB20","unstructured":"H. Zhang, H. Shen, New exact algorithms for MAX-2-SAT. Submitted to International Workshop on First-order Theorem Proving (FTP 2003)."}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004640?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004640?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T03:45:16Z","timestamp":1734579916000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304004640"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":20,"alternative-id":["S1571065304004640"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00464-0","relation":{},"ISSN":["1571-0653"],"issn-type":[{"type":"print","value":"1571-0653"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}