{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:58Z","timestamp":1759638958566},"reference-count":45,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,8,1]],"date-time":"2003-08-01T00:00:00Z","timestamp":1059696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3674,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2003,8]]},"DOI":"10.1016\/s0166-218x(02)00404-3","type":"journal-article","created":{"date-parts":[[2003,7,16]],"date-time":"2003-07-16T10:54:32Z","timestamp":1058352872000},"page":"173-184","source":"Crossref","is-referenced-by-count":14,"title":["Worst-case study of local search for MAX-k-SAT"],"prefix":"10.1016","volume":"130","author":[{"given":"Edward A.","family":"Hirsch","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00404-3_BIB1","series-title":"Approximation Algorithms for NP-hard Problems","article-title":"Hardness of approximation","author":"Arora","year":"1997"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB2","unstructured":"T. Asano, D.P. Williamson, Improved approximation algorithms for MAX SAT, in: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201900, 2000, pp. 96\u2013105."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB3","series-title":"Proceedings of the 10th International Symposium on Algorithms and Computation, ISAAC\u201999","first-page":"247","article-title":"Upper bounds for MaxSat: further improved","volume":"Vol. 1741","author":"Bansal","year":"1999"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB4","doi-asserted-by":"crossref","unstructured":"R. Battiti, M. Protassi, Reactive search, a history-sensitive heuristic for MAX-SAT, ACM J. Exp. Algorithmics 2 (1997) (Paper 2).","DOI":"10.1145\/264216.264220"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB5","doi-asserted-by":"crossref","unstructured":"R. Battiti, M. Protasi, Approximate algorithms and heuristics for MAX-SAT, in: Handbook of Combinatorial Optimization, Vol. 1, Kluwer Academic Publishers, Dordrecht, 1998, pp. 77\u2013148.","DOI":"10.1007\/978-1-4613-0303-9_2"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB6","unstructured":"R. Bayardo, R. Schrag, Using CSP look-back techniques to solve real-world SAT instances, in: Proceedings of the 14th National Conference on Artificial Intelligence, AAAI\u201997, pp. 203\u2013208."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB7","doi-asserted-by":"crossref","unstructured":"E. Dantsin, Two propositional proof systems based on the splitting method, Zapiski Nauchnykh Seminarov LOMI 105 (1981) 24\u201344 (English translation: J. Soviet Math. 22(3) (1983) 1293\u20131305) (in Russian).","DOI":"10.1007\/BF01084392"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB8","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, Ann. Pure Appl. Logic, 2001, to appear; Preliminary version: approximation algorithms for MAX SAT: a better performance ratio at the cost of a longer running time, PDMI preprint 14\/1998, Steklov Institute of Mathematics at St.Petersburg, 1998. Electronic address: ftp:\/\/ftp.pdmi.ras.ru\/pub\/publicat\/preprint\/1998\/14-98.ps.gz."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB9","series-title":"Proceedings of the 27th International Colloquium on Automata, Languages and Programming","first-page":"236","article-title":"Deterministic algorithms for k-SAT based on covering codes and local search","volume":"Vol. 1853","author":"Dantsin","year":"2000"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB10","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\u22122\/(k+1))n algorithm for k-SAT based on local search, Theoret. Comput. Sci., 2002, to appear.","DOI":"10.1016\/S0304-3975(01)00174-8"},{"issue":"7","key":"10.1016\/S0166-218X(02)00404-3_BIB11","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theorem-proving","volume":"5","author":"Davis","year":"1962","journal-title":"Comm. ACM"},{"issue":"3","key":"10.1016\/S0166-218X(02)00404-3_BIB12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB13","doi-asserted-by":"crossref","unstructured":"U. Feige, M.X. Goemans, Approximating the value of two proper proof systems, with applications to MAX-2SAT and MAX-DICUT, in: Proceedings of the Third Israel Symposium on Theory and Computing Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB14","unstructured":"I.P. Gent, T. Walsh, Towards an understanding of hill-climbing procedures for SAT, in: Proceedings of the 11th National Conference on Artificial Intelligence, AAAI\u201993, AAAI Press, New York, pp. 28\u201333."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB15","unstructured":"I.P. Gent, T. Walsh, Unsatisfied variables in local search, in: J. Hallam (Ed.), Hybrid Problems, Hybrid Solutions, IOS Press, 1995, pp. 73\u201385."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB16","unstructured":"J. Gramm, E.A. Hirsch, R. Niedermeier, P. Rossmanith, New worst-case upper bounds for MAX-2-SAT with application to MAX-CUT, Technical Report 00-037, Electronic Colloquium on Computational Complexity, June 2000, Electronic address: ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2000\/TR00-037\/index.html, Discrete Appl. Math., to appear."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB17","series-title":"Proceedings of the Fourth Italian Conference on Algorithms and Complexity, CIAC 2000","first-page":"174","article-title":"Faster exact solutions for Max-2-Sat","volume":"Vol. 1767","author":"Gramm","year":"2000"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB18","series-title":"The Satisfiability Problem: Theory and Applications (DIMACS Workshop March 11\u201313, 1996)","first-page":"19","article-title":"Algorithms for satisfiability (SAT) problem: a survey","volume":"Vol. 35","author":"Gu","year":"1997"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB19","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\/S0166-218X(02)00404-3_BIB20","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal inapproximability results, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC\u201997, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB21","unstructured":"E.A. Hirsch, A 2K\/4-time algorithm for MAX-2-SAT: corrected version. Technical Report 99-036, Revision 02, Electronic Colloquium on Computational Complexity, f\u00e9vrier 2000. Electronic address: ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/1999\/TR99-036\/revisn02.ps."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB22","doi-asserted-by":"crossref","unstructured":"E.A. Hirsch, A new algorithm for MAX-2-SAT, in: H. Reichel, S. Tison (Eds.), Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lecture Notes in Computer Science, Vol. 1770, Springer, Berlin, 2000, pp. 65\u201373. (Contains an error, fixed in [21]).","DOI":"10.1007\/3-540-46541-3_5"},{"issue":"4","key":"10.1016\/S0166-218X(02)00404-3_BIB23","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":"J. Automat. Reason."},{"issue":"1\/2","key":"10.1016\/S0166-218X(02)00404-3_BIB24","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1023\/A:1006318521185","article-title":"SAT local search algorithms","volume":"24","author":"Hirsch","year":"2000","journal-title":"J. Automat. Reason."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB25","series-title":"Proceedings of the seventh International Conference on Principles and Practice of Constraint Programming, CP\u201901","first-page":"605","article-title":"Solving Boolean satisfiability using local search guided by unit clause elimination","volume":"Vol. 2239","author":"Hirsch","year":"2001"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB26","unstructured":"H.H. Hoos, On the run-time behaviour of stochastic local search algorithms for SAT, in: Proceedings of the 16th National Conference on Artificial Intelligence, AAAI\u201999, 1999, pp. 661\u2013666."},{"issue":"4","key":"10.1016\/S0166-218X(02)00404-3_BIB27","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1023\/A:1006350622830","article-title":"Local search algorithms for SAT","volume":"24","author":"Hoos","year":"2000","journal-title":"J. Automat. Reason."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB28","doi-asserted-by":"crossref","unstructured":"H. Karloff, U. Zwick, A 7\/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201997, 1997, pp. 406\u2013415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB29","series-title":"The Satisfiability Problem: Theory and Applications (DIMACS Workshop March 11\u201313, 1996)","first-page":"573","article-title":"A general stochastic approach to solving problems with hard and soft constraints","volume":"Vol. 35","author":"Kautz","year":"1997"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB30","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","article-title":"Parameterizing above guaranteed values","volume":"31","author":"Mahajan","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB31","unstructured":"D. McAllester, B. Selman, H. Kautz, Evidence in invariants for local search, in: Proceedings of the AAAI\u201997, 1997, pp. 321\u2013326."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB32","unstructured":"B. Monien, E. Speckenmeyer, 3-satisfiability is testable in O(1.62r) steps, Technical Report Bericht No. 3\/1979, Reihe Theoretische Informatik, Universit\u00e4t-Gesamthochschule-Paderborn, 1979."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB33","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","article-title":"Solving satisfiability in less then 2n steps","volume":"10","author":"Monien","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB34","doi-asserted-by":"crossref","unstructured":"M. Moskewicz, C. Madigan, Y. Zhao, L. Zhang, S. Malik, Chaff: engineering an efficient SAT solver, in: Proceedings of the 39th Design Automation Conference, 2001, to appear.","DOI":"10.1145\/378239.379017"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB35","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":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB36","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou, On selecting a satisfying truth assignment, in: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201991, 1991, pp. 163\u2013169.","DOI":"10.1109\/SFCS.1991.185365"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB37","unstructured":"A.J. Parkes, J. Walser, Tuning local search for satisability testing, in: Proceedings of the 13th National Conference on Artificial Intelligence, AAAI\u201996, 1996, pp. 356\u2013362."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB38","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudl\u00e1k, M.E. Saks, F. Zane, An improved exponential-time algorithm for k-SAT, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201998, 1998, pp. 628\u2013637.","DOI":"10.1109\/SFCS.1998.743513"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB39","series-title":"The Satisfiability Problem: Theory and Applications (DIMACS Workshop March 11\u201313, 1996)","first-page":"393","article-title":"Approximate solution of weighted MAX-SAT problems using GRASP","volume":"Vol. 35","author":"Resende","year":"1997"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB40","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201999, 1999, pp. 410\u2013414.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB41","unstructured":"B. Selman, H.A. Kautz, B. Cohen, Noise strategies for improving local search, in: Proceedings of the 12th National Conference on Artificial Intelligence, AAAI\u201994, 1994, pp. 337\u2013343."},{"issue":"3","key":"10.1016\/S0166-218X(02)00404-3_BIB42","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1006\/jagm.1994.1045","article-title":"On the approximation of maximum satisfiability","volume":"17","author":"Yannakakis","year":"1994","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB43","unstructured":"L. Zhang, zChaff. An implementation of the Chaff solver. Available from http:\/\/www.ee.princeton.edu\/~chaff\/zchaff.html."},{"key":"10.1016\/S0166-218X(02)00404-3_BIB44","doi-asserted-by":"crossref","unstructured":"U. Zwick, Finding almost satisfying assignments, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, STOC\u201998, 1998, pp. 551\u2013560.","DOI":"10.1145\/276698.276869"},{"key":"10.1016\/S0166-218X(02)00404-3_BIB45","unstructured":"U. Zwick, Computer assisted proof of spherical volume inequalities, Manuscript, 2001, p. 21."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004043?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X02004043?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,17]],"date-time":"2019-03-17T09:51:36Z","timestamp":1552816296000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X02004043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0166218X02004043"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00404-3","relation":{},"ISSN":["0166-218X"],"issn-type":[{"type":"print","value":"0166-218X"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}