{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:51Z","timestamp":1759639011461},"reference-count":39,"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)00402-x","type":"journal-article","created":{"date-parts":[[2003,2,12]],"date-time":"2003-02-12T01:10:51Z","timestamp":1045012251000},"page":"139-155","source":"Crossref","is-referenced-by-count":43,"title":["Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT"],"prefix":"10.1016","volume":"130","author":[{"given":"Jens","family":"Gramm","sequence":"first","affiliation":[]},{"given":"Edward A.","family":"Hirsch","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(02)00402-X_BIB1","unstructured":"S. Arora, C. Lund, Hardness of approximation, in: D. Hochbaum (Ed.), Approximation Algorithms for NP-Hard Problems, Chapter 10, PWS Publishing Company, Boston, 1997, pp. 399\u2013446."},{"key":"10.1016\/S0166-218X(02)00402-X_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)00402-X_BIB3","doi-asserted-by":"crossref","unstructured":"G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation\u2014Combinatorial Optimization Problems and their Approximability Properties, Springer, Berlin, 1999.","DOI":"10.1007\/978-3-642-58412-1"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB4","doi-asserted-by":"crossref","unstructured":"N. Bansal, V. Raman, Upper bounds for MaxSat: further improved, in: A. Aggarwal, C. Pandu Rangan (Eds.), Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC\u201999, Lecture Notes in Computer Science, Vol. 174, Springer, Berlin, 1999, pp. 247\u2013258.","DOI":"10.1007\/3-540-46632-0_26"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB5","unstructured":"R. Beigel, Finding maximum independent sets in sparse and general graphs, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201999, 1999, pp. 856\u2013857."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB6","unstructured":"P. Berman, M. Karpinski, On some tighter inapproximability results, in: Proceedings of the 26th International Colloquium on Automata, Languages and Programming, ICALP\u201999, Lecture Notes in Computer Science, Vol. 1644, Springer, Berlin, 1999, pp. 200\u2013209."},{"issue":"4","key":"10.1016\/S0166-218X(02)00402-X_BIB7","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\/S0166-218X(02)00402-X_BIB8","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1997.1490","article-title":"On fixed-parameter tractability and approximability of NP optimization problems","volume":"54","author":"Cai","year":"1997","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB9","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 Ser. Discrete Math. Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB10","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\/S0166-218X(02)00402-X_BIB11","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/S0168-0072(01)00052-5","article-title":"MAX SAT approximation beyond the limits of polynomial-time approximation","volume":"113","author":"Dantsin","year":"2001","journal-title":"Ann. Pure Appl. Logic"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB12","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"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB13","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: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP\u201900, Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 236\u2013243.","DOI":"10.1007\/3-540-45022-X_21"},{"issue":"7","key":"10.1016\/S0166-218X(02)00402-X_BIB14","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)00402-X_BIB15","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)00402-X_BIB16","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB17","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)00402-X_BIB18","unstructured":"J. Gramm, Exact algorithms for Max2Sat and their applications, Diploma thesis, WSI f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, October 1999, available from http:\/\/www-fs.informatik.uni-tuebingen.de\/~gramm\/publications\/."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB19","unstructured":"J. Gramm, R. Niedermeier, Faster exact solutions for Max-2-Sat, in: Proceedings of the Fourth Italian Conference on Algorithms and Complexity, CIAC 2000, Lecture Notes in Computer Science, Vol. 1767, Springer, Berlin, 2000, pp. 174\u2013186."},{"key":"10.1016\/S0166-218X(02)00402-X_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, Journal of the ACT 48 (2001) 798\u2013859.","DOI":"10.1145\/502090.502098"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB21","unstructured":"E.A. Hirsch, A 2K\/4-time algorithm for MAX-2-SAT: Corrected version, Technical Report 99-036, Revision 02, Electronic Colloquim on Computational Complexity, February 2000, electronic address: ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/1999\/TR99-036\/revisn02.ps."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB22","doi-asserted-by":"crossref","unstructured":"E.A. Hirsch, A new algorithm for MAX-2-SAT, in: Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lecture Notes in Computer Science, Vol. 1770, Springer-Verlag, Berlin, February 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)00402-X_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."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB24","unstructured":"E.A. Hirsch, Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search, in: Proceedings of RANDOM 2000, ICALP Workshops 2000, Proceedings in Informatics, Vol. 8, 2000, pp. 69\u201376."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB25","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"},{"issue":"1\u20132","key":"10.1016\/S0166-218X(02)00402-X_BIB26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","article-title":"New methods for 3-SAT decision and worst-case analysis","volume":"223","author":"Kullmann","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB27","unstructured":"O. Kullmann, H. Luckhardt, Algorithms for SAT\/TAUT decision based on various measures. preprint, 71 pages, available from http:\/\/www.cs.toronto.edu\/~kullmann February 1999."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB28","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)00402-X_BIB29","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)00402-X_BIB30","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jagm.2000.1075","article-title":"New upper bounds for MaxSat","volume":"36","author":"Niedermeier","year":"2000","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB31","series-title":"Computational Complexity","author":"Papadimitriou","year":"1994"},{"key":"10.1016\/S0166-218X(02)00402-X_BIB32","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)00402-X_BIB33","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/dimacs\/020\/04","article-title":"Maximum cuts and large bipartite subgraphs","volume":"20","author":"Poljak","year":"1995","journal-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci."},{"issue":"1","key":"10.1016\/S0166-218X(02)00402-X_BIB34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","article-title":"A simplified NP-complete MAXSAT problem","volume":"65","author":"Raman","year":"1998","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB35","first-page":"77","article-title":"Generalized resolution principle","volume":"3","author":"Robinson","year":"1968","journal-title":"Mac. Intell."},{"key":"10.1016\/S0166-218X(02)00402-X_BIB36","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)00402-X_BIB37","doi-asserted-by":"crossref","unstructured":"R. Schuler, U. Sch\u00f6ning, O. Watnabe, T. Hofemister, A probabilistic {3-SAT} algorithm further improved, Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science, STACS 2002, Lecture Notes in Computer Science, 2285, Springer, 2002, 192\u2013202.","DOI":"10.1007\/3-540-45841-7_15"},{"issue":"3","key":"10.1016\/S0166-218X(02)00402-X_BIB38","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)00402-X_BIB39","unstructured":"U. Zwick, personal communication, 2000."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0200402X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X0200402X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T13:12:11Z","timestamp":1584018731000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X0200402X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0166218X0200402X"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(02)00402-x","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}