{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T22:14:11Z","timestamp":1794348851377,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540745099","type":"print"},{"value":"9783540745105","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74510-5_21","type":"book-chapter","created":{"date-parts":[[2007,8,21]],"date-time":"2007-08-21T11:11:35Z","timestamp":1187694695000},"page":"194-204","source":"Crossref","is-referenced-by-count":11,"title":["New Bounds for MAX-SAT by Clause Learning"],"prefix":"10.1007","author":[{"given":"Alexander S.","family":"Kulikov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Konstantin","family":"Kutzkov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"21_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1007\/978-3-540-24605-3_25","volume-title":"Theory and Applications of Satisfiability Testing","author":"R. Williams","year":"2004","unstructured":"Williams, R.: On computing k-CNF formula properties. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 330\u2013340. Springer, Heidelberg (2004)"},{"issue":"3","key":"21_CR2","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J. Robson","year":"1986","unstructured":"Robson, J.: Algorithms for maximum independent sets. Journal of Algorithms\u00a07(3), 425\u2013440 (1986)","journal-title":"Journal of Algorithms"},{"issue":"5","key":"21_CR3","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1109\/12.769433","volume":"48","author":"J. Marques-Silva","year":"1999","unstructured":"Marques-Silva, J., Sakallah, K.: Grasp: a search algorithm for propositional satisfiability. IEEE Transactionon Computers\u00a048(5), 506\u2013521 (1999)","journal-title":"IEEE Transactionon Computers"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S.: Chaff: engineering an efficient SAT solver. In: Proceedings of the 38th Design Automation Conference, pp. 530\u2013535 (2001)","DOI":"10.1145\/378239.379017"},{"key":"21_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/3-540-63104-6_28","volume-title":"Automated Deduction - CADE-14","author":"H. Zhang","year":"1997","unstructured":"Zhang, H.: Sato: An efficient propositional prover. In: McCune, W. (ed.) Automated Deduction - CADE-14. LNCS, vol.\u00a01249, pp. 272\u2013275. Springer, Heidelberg (1997)"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1109\/CCC.2003.1214425","volume-title":"Proceedings of 18th IEEE Annual Conference on Computational Complexity","author":"P. Beame","year":"2003","unstructured":"Beame, P., Impagliazzo, R., Pitassi, T., Segerlind, N.: Memoization and DPLL: formula caching proof systems. In: Proceedings of 18th IEEE Annual Conference on Computational Complexity, pp. 248\u2013259. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/11814948_26","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"E. Dantsin","year":"2006","unstructured":"Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in O(2 n ) time. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 266\u2013276. Springer, Heidelberg (2006)"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R. Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science\u00a0348, 357\u2013365 (2005)","journal-title":"Theoretical Computer Science"},{"key":"21_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/3-540-48523-6_54","volume-title":"Automata, Languages and Programming","author":"R. Niedermeier","year":"1999","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for MaxSat. In: Wiedermann, J., van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol.\u00a01644, pp. 575\u2013585. Springer, Heidelberg (1999)"},{"key":"21_CR10","unstructured":"Hirsch, E.A.: A 2K\/4-time algorithm for MAX-2-SAT: Corrected version. ECCC Report TR99-036, Revision 02 (2000)"},{"issue":"2","key":"21_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-540-45198-3_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Scott","year":"2003","unstructured":"Scott, A., Sorkin, G.: Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 382\u2013395. Springer, Heidelberg (2003)"},{"key":"21_CR13","unstructured":"Kneis, J., Rossmanith, P.: A new satisfiability algorithm with applications to Max-Cut. Technical Report AIB2005-08, Dept. of Computer Science, RWTH Aachen University (2005)"},{"key":"21_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1109557.1109559","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Kojevnikov","year":"2006","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 11\u201317. ACM Press, New York (2006)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Kneis, J., Moelle, D., Richter, S., Rossmanith, P.: Algorithms based on the treewidth of sparse graphs. In: Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science. LNCS, pp. 385\u2013396 (2005)","DOI":"10.1007\/11604686_34"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-SAT and Max 2-CSP. Discrete Optimization 2006 (to appear)","DOI":"10.1016\/j.disopt.2007.08.001"},{"key":"21_CR17","unstructured":"Kullmann, O., Luckhardt, H.: Algorithms for SAT\/TAUT decision based on various measures (preprint)"},{"key":"21_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1007\/11499107_35","volume-title":"Theory and Applications of Satisfiability Testing","author":"A.S. Kulikov","year":"2005","unstructured":"Kulikov, A.S.: Automated generation of simplification rules for SAT and MAXSAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 430\u2013436. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74510-5_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:21:50Z","timestamp":1619504510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74510-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745099","9783540745105"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74510-5_21","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-540-74510-5","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}