{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:33Z","timestamp":1725470733641},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_53","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"588-599","source":"Crossref","is-referenced-by-count":1,"title":["An LP-Designed Algorithm for Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Alexander D.","family":"Scott","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"53_CR1","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R. Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289\n                    n\n                  ). J. Algorithms\u00a054(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"issue":"2","key":"53_CR2","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 Appl. Math.\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Appl. Math."},{"key":"53_CR3","unstructured":"Kulikov, A.S., Fedin, S.S.: Solution of the maximum cut problem in time 2\u2009\u2223\u2009E\u2009\u2223\u2009\/4, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 293 (7), 129\u2013138, 183 (2002), Teor. Slozhn. Vychisl."},{"key":"53_CR4","unstructured":"Kneis, J., Rossmanith, P.: A new satisfiability algorithm with applications to Max-Cut, Tech. Report AIB-2005-08, Department of Computer Science, RWTH Aachen (2005)"},{"key":"53_CR5","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.D. Scott","year":"2003","unstructured":"Scott, A.D., Sorkin, G.B.: 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":"53_CR6","unstructured":"Scott, A.D., Sorkin, G.B.: A faster exponential-time algorithm for Max 2-Sat, Max Cut, and Max k-Cut, Tech. Report RC23456 (W0412-001), IBM Research Report (December 2004), See: \n                    \n                      http:\/\/domino.research.ibm.com\/library\/cyberdig.nsf"},{"key":"53_CR7","unstructured":"Scott, A.D., Sorkin, G.B.: Generalized constraint satisfaction problems, Tech. Report RC23935, IBM Research Report (April 2006), See: \n                    \n                      http:\/\/domino.research.ibm.com\/library\/cyberdig.nsf"},{"issue":"6","key":"53_CR8","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L. Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput.\u00a029(6), 2074\u20132097 (2000)","journal-title":"SIAM J. Comput."},{"key":"53_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1007\/978-3-540-27836-8_101","volume-title":"Automata, Languages and Programming","author":"R. Williams","year":"2004","unstructured":"Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1227\u20131237. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:57Z","timestamp":1619507817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/11841036_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}