{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:12Z","timestamp":1794381072258,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_101","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"1227-1237","source":"Crossref","is-referenced-by-count":42,"title":["A New Algorithm for Optimal Constraint Satisfaction and Its Implications"],"prefix":"10.1007","author":[{"given":"Ryan","family":"Williams","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"101_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"Alber, J., Gramm, J., Niedermeier, R.: Faster exact algorithms for hard problems: a parameterized point of view. Discrete Mathematics\u00a0229, 3\u201327 (2001)","journal-title":"Discrete Mathematics"},{"key":"101_CR2","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica\u00a016, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"101_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Algorithms and Computations","author":"N. Bansal","year":"1999","unstructured":"Bansal, N., Raman, V.: Upper bounds for Max-Sat: Further Improved. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 247\u2013258. Springer, Heidelberg (1999)"},{"key":"101_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-45465-9_39","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Indyk, P., Panigrahy, R.: New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 451\u2013462. Springer, Heidelberg (2002)"},{"key":"101_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-45995-2_32","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Chen","year":"2002","unstructured":"Chen, J., Kanj, I.: Improved Exact Algorithms for MAX-SAT. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 341\u2013355. Springer, Heidelberg (2002)"},{"issue":"3","key":"101_CR6","first-page":"251","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. JSC\u00a09(3), 251\u2013280 (1990)","journal-title":"JSC"},{"key":"101_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-46521-9_15","volume-title":"Algorithms and Complexity","author":"J. Gramm","year":"2000","unstructured":"Gramm, J., Niedermeier, R.: Faster exact solutions for Max2Sat. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 174\u2013186. Springer, Heidelberg (2000)"},{"issue":"2","key":"101_CR8","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 application to MAX-CUT. Discrete Applied Mathematics\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"1-3","key":"101_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0168-0072(01)00052-5","volume":"113","author":"E. Dantsin","year":"2001","unstructured":"Dantsin, E., Gavrilovich, M., Hirsch, E.A., Konev, B.: MAX-SAT approximation beyond the limits of polynomial-time approximation. Annals of Pure and Applied Logic\u00a0113(1-3), 81\u201394 (2001)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"101_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0166-218X(02)00404-3","volume":"130","author":"E.A. Hirsch","year":"2003","unstructured":"Hirsch, E.A.: Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics\u00a0130(2), 173\u2013184 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"101_CR11","unstructured":"Hirsch, E.A.: A 2m\/4-time Algorithm for MAX-2-SAT: Corrected Version. Electronic Colloquium on Computational Complexity Report TR99-036 (2000)"},{"key":"101_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-45841-7_15","volume-title":"STACS 2002","author":"T. Hofmeister","year":"2002","unstructured":"Hofmeister, T., Sch\u00f6ning, U., Schuler, R., Watanabe, O.: A probabilistic 3-SAT algorithm further improved. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 192\u2013202. Springer, Heidelberg (2002)"},{"key":"101_CR13","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. JACM\u00a021, 277\u2013292 (1974)","journal-title":"JACM"},{"issue":"4","key":"101_CR14","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Computing\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM J. Computing"},{"key":"101_CR15","unstructured":"Kulikov, A.S., Fedin, S.S.: A 2|E|\/4-time Algorithm for MAX-CUT. Zapiski nauchnyh seminarov POMI No.293, 129\u2013138 (2002)"},{"issue":"2","key":"101_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above Guaranteed Values: MAXSAT and MAXCUT. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"101_CR17","first-page":"415","volume":"26","author":"J. Nesetril","year":"1985","unstructured":"Nesetril, J., Poljak, S.: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae\u00a026(2), 415\u2013419 (1985)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"101_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"26","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms\u00a026, 63\u201388 (2000)","journal-title":"J. Algorithms"},{"key":"101_CR19","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudlak, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for k-SAT. In: Proceedings of the 39th IEEE FOCS, pp. 628\u2013637 (1998)","DOI":"10.1109\/SFCS.1998.743513"},{"key":"101_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V. Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Srinivasa Rao, S.: A Simplified NP-Complete MAXSAT problem. Information Processing Letters\u00a065, 1\u20136 (1998)","journal-title":"Information Processing Letters"},{"key":"101_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0205003","volume":"5","author":"R. Rivest","year":"1976","unstructured":"Rivest, R.: Partial match retrieval algorithms. SIAM J. on Computing\u00a05, 19\u201350 (1976)","journal-title":"SIAM J. on Computing"},{"issue":"3","key":"101_CR22","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"M. Robson","year":"1986","unstructured":"Robson, M.: Algorithms for maximum independent sets. J. Algorithms\u00a07(3), 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"101_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/3-540-57568-5_250","volume-title":"Algorithms and Computation","author":"F. Ruskey","year":"1993","unstructured":"Ruskey, F.: Simple combinatorial Gray codes constructed by reversing sublists. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 201\u2013208. Springer, Heidelberg (1993)"},{"key":"101_CR24","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings of the 40th IEEE FOCS, pp. 410\u2013414 (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"issue":"3","key":"101_CR25","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T=O(2n\/2), S=O(2n\/4) Algorithm for Certain NP-Complete Problems. SIAM J. Comput.\u00a010(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"key":"101_CR26","unstructured":"Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. Accepted in J. Algorithms (2003)"},{"key":"101_CR27","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":"101_CR28","doi-asserted-by":"crossref","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. Electronic Colloquium on Computational Complexity, Report TR04-032 (2004)","DOI":"10.1007\/978-3-540-27836-8_101"},{"key":"101_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"},{"issue":"3","key":"101_CR30","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All Pairs Shortest Paths using bridging sets and rectangular matrix multiplication. JACM\u00a049(3), 289\u2013317 (2002)","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_101.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T20:30:20Z","timestamp":1636489820000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_101","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}