{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:20:29Z","timestamp":1737436829892,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_9","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"87-95","source":"Crossref","is-referenced-by-count":3,"title":["New Algorithms for k-SAT Based on the Local Search Principle"],"prefix":"10.1007","author":[{"given":"Uwe","family":"Sch\u00f6ning","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"B. Aspvall, M. F. Plass, R. E. Tarjan: A linear time algorithm for testing the truth of certain quantified Boolean formulas, Information Processing Letters 8(3) (1979) 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"9_CR2","unstructured":"R. B. Ash: Information Theory. Dover 1965."},{"key":"9_CR3","unstructured":"G. Cohen, I. Honkala, S. Litsyn, A. Lobstein: Covering Codes. North-Holland 1997."},{"key":"9_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45022-X_21","volume-title":"Proc. 27th International Colloquium on Automata, Languages and Programming 2000","author":"E. Dantsin","year":"2000","unstructured":"E. Dantsin, A. Goerdt, E. A. Hirsch, U. Sch\u00f6ning: Deterministic algorithms for k-SAT based on covering codes and local search. Proc. 27th International Colloquium on Automata, Languages and Programming 2000. Springer Lecture Notes in Computer Science, Vol. 1853, pages 236\u2013247, 2000."},{"key":"9_CR5","unstructured":"E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Sch\u00f6ning: A deterministic $$ (2 - \\tfrac{2} {{k + 1}})^n $$ algorithm for k-SAT based on local search. To appear in Theoretical Computer Science."},{"key":"9_CR6","unstructured":"G. R. Grimmett, D. R. Stirzaker: Probability and Random Processes. Oxford University Press, 2nd Edition, 1992."},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"D. S. Hochbaum (ed.): Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.","DOI":"10.1145\/261342.571216"},{"key":"9_CR8","unstructured":"T. Hofmeister, U. Sch\u00f6ning, R. Schuler, O. Watanabe: A probabilistic 3-SAT algorithm further improved. submitted."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"O. Kullmann: New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science 223 (1999) 1\u201372.","journal-title":"Theoretical Computer Science"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","volume":"10","author":"B. Monien","year":"1985","unstructured":"B. Monien, E. Speckenmeyer: Solving satisfiability in less than 2n steps. Discrete Applied Mathematics 10 (1985) 287\u2013295.","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou: On selecting a satisfying truth assignment. Proceedings of the 32nd Ann. IEEE Symp. on Foundations of Computer Science, 163\u2013169, 1991.","DOI":"10.1109\/SFCS.1991.185365"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudl\u00e1k, F. Zane: Satisfiability coding lemma. Proceedings 38th IEEE Symposium on Foundations of Computer Science 1997, 566\u2013574.","DOI":"10.1109\/SFCS.1997.646146"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudl\u00e1k, M. E. Saks, F. Zane: An improved exponential-time algorithm for k-SAT. Proceedings 39th IEEE Symposium on Foundations of Computer Science 1998, 628\u2013637.","DOI":"10.1109\/SFCS.1998.743513"},{"key":"9_CR14","unstructured":"U. Sch\u00f6ning: On The Complexity Of Constraint Satisfaction Problems. Ulmer Informatik-Berichte, Nr. 99-03. Universit\u00e4t Ulm, Fakult\u00e4t f\u00fcr Informatik, 1999."},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning: A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceedings 40th IEEE Symposium on Foundations of Computer Science 1999, 410\u2013414.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"9_CR16","unstructured":"U. Sch\u00f6ning: A probabilistic algorithm for k-SAT based on limited local search and restart. To appear in Algorithmica."},{"key":"9_CR17","unstructured":"R. Schuler, U. Sch\u00f6ning, O. Watanabe: An Improved Randomized Algorithm For 3-SAT. Techn. Report TR-C146, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2001."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:28:33Z","timestamp":1737397713000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}