{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T10:04:08Z","timestamp":1751882648579},"reference-count":20,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2001,12,1]],"date-time":"2001-12-01T00:00:00Z","timestamp":1007164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4246,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annals of Pure and Applied Logic"],"published-print":{"date-parts":[[2001,12]]},"DOI":"10.1016\/s0168-0072(01)00052-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T13:36:39Z","timestamp":1027604199000},"page":"81-94","source":"Crossref","is-referenced-by-count":17,"title":["MAX SAT approximation beyond the limits of polynomial-time approximation"],"prefix":"10.1016","volume":"113","author":[{"given":"Evgeny","family":"Dantsin","sequence":"first","affiliation":[]},{"given":"Michael","family":"Gavrilovich","sequence":"additional","affiliation":[]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[]},{"given":"Boris","family":"Konev","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0168-0072(01)00052-5_BIB1","unstructured":"S. Arora, C. Lund, Hardness of approximation, in: D. Hochbaum (Ed.), Approximation Algorithms for NP-hard Problems, Chap. 10., PWS Publishing Company, Boston, 1997."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB2","unstructured":"T. Asano, D.P. Williamson, Improved approximation algorithms for MAX SAT, Proc. 11th Annu. ACM-SIAM Symp. on Discrete Algorithms, SODA\u201900, 2000, pp. 96\u2013105."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB3","unstructured":"N. Bansal, V. Raman, Upper bounds for MaxSat: further improved, in: A. Aggarwal, C. Pandu Rangan (Eds.), Proc. 10th Internat. Symp. on Algorithms and Computation, ISAAC\u201999, Lecture Notes in Computer Science, vol. 1741, Springer, Berlin, December 1999, pp. 247\u2013258."},{"issue":"4","key":"10.1016\/S0168-0072(01)00052-5_BIB4","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":"J. Combin. Optim."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB5","doi-asserted-by":"crossref","unstructured":"E. Dantsin, Two propositional proof systems based on the splitting method. Zapiski Nauchnykh Seminarov LOMI 105 (1981) 24\u201344. (in Russian) (English translation: J. Soviet Math. 22 (3) (1983) 1293\u20131305.)","DOI":"10.1007\/BF01084392"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB6","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, Preprint 14\/1998, Steklov Institute of Mathematics at St. Petersburg, May 1998, http:\/\/www.pdmi.ras.ru\/preprint\/1998\/index.html."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB7","doi-asserted-by":"crossref","unstructured":"E. Dantsin, A. Goerdt, E.A. Hirsch, U. Sch\u00f6ning, Deterministic algorithms for k-SAT based on covering codes and local search, in: U. Montanari, J.D.P. Rolim, E. Welzl (Eds.), Proc. 27th Internat. Colloq. on Automata, Languages and Programming, ICALP\u20192000, Lecture Notes in Computer Science, vol. 1853, Springer, Berlin, 2000.","DOI":"10.1007\/3-540-45022-X_21"},{"issue":"7","key":"10.1016\/S0168-0072(01)00052-5_BIB8","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"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB9","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, Proc. 3rd Israel Symp. on Theory and Computing Systems, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"issue":"6","key":"10.1016\/S0168-0072(01)00052-5_BIB10","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB11","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 Colloquim on Computational Complexity, June 2000, ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2000\/TR00-037\/index.html."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB12","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Some optimal inapproximability results. Proc. 29th Annu. ACM Symp. on Theory of Computing, STOC\u201997, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"issue":"4","key":"10.1016\/S0168-0072(01)00052-5_BIB13","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."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB14","unstructured":"E.A. Hirsch, Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search, Proc. RANDOM 2000, ICALP Workshops 2000, Proc. in Informatics 8:69\u201376, Carleton Scientific 2000, Preliminary version available as Technical Report 00-019, Electronic Colloquim on Computational Complexity, 2000, ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2000\/TR00-019\/index.html."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB15","doi-asserted-by":"crossref","unstructured":"H. Karloff, U. Zwick, A 7\/8-approximation algorithm for MAX 3SAT?, Proc. 38th Annu. IEEE Symp. on Foundations of Computer Science, FOCS\u201997, 1997, pp. 406\u2013415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB16","unstructured":"O. Kullmann, H. Luckhardt, Deciding propositional tautologies: algorithms and their complexity, Preprint, January 1997, 82pp., http:\/\/www.cs.toronto.edu\/\u00a0\u0303kullmann."},{"key":"10.1016\/S0168-0072(01)00052-5_BIB17","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":"J. Algorithms"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB18","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\/S0168-0072(01)00052-5_BIB19","doi-asserted-by":"crossref","unstructured":"R. Niedermeier, P. Rossmanith, New upper bounds for MaxSat, J. Algorithms, 2000, in preparation. (Preliminary version appeared in Proc. ICALP\u201999.)","DOI":"10.1006\/jagm.2000.1075"},{"key":"10.1016\/S0168-0072(01)00052-5_BIB20","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, Proc. 40th Annu. IEEE Symp. on Foundations of Computer Science, FOCS\u201999, 1999, pp. 410\u2013414.","DOI":"10.1109\/SFFCS.1999.814612"}],"container-title":["Annals of Pure and Applied Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0168007201000525?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0168007201000525?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T08:25:49Z","timestamp":1556526349000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0168007201000525"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":20,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["S0168007201000525"],"URL":"https:\/\/doi.org\/10.1016\/s0168-0072(01)00052-5","relation":{},"ISSN":["0168-0072"],"issn-type":[{"value":"0168-0072","type":"print"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}