{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:48Z","timestamp":1759637688237},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540407706"},{"type":"electronic","value":"9783540451983"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_32","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"382-395","source":"Crossref","is-referenced-by-count":19,"title":["Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances"],"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":"3","key":"32_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/rsa.1006","volume":"18","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B., Borgs, C., Chayes, J.T., Kim, J.H., Wilson, D.B.: The scaling window of the 2-SAT transition. Random Structures Algorithms\u00a018(3), 201\u2013256 (2001)","journal-title":"Random Structures Algorithms"},{"key":"32_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random graphs","author":"B. Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random graphs. Cambridge Studies in Advanced Mathematics, vol.\u00a073. Cambridge University Press, Cambridge (2001)"},{"key":"32_CR3","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.B.: Random MAX SAT, random MAX CUT, and their phase transitions, 49 pages (submitted for publication)"},{"key":"32_CR4","volume-title":"Proceedings of the 14th Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"D. Coppersmith","year":"2003","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M., Sorkin, G.B.: Random MAX SAT, random MAX CUT, and their phase transitions. In: Proceedings of the 14th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, Baltimore, MD. ACM, New York (2003)"},{"key":"32_CR5","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: Max k-cut and approximating the chromatic number of random graphs (to appear)"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1109\/SFCS.1992.267789","volume-title":"33th Annual Symposium on Foundations of Computer Science","author":"V. Chv\u00e1tal","year":"1992","unstructured":"Chv\u00e1tal, V., Reed, B.: Mick gets some (the odds are on his side). In: 33th Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, pp. 620\u2013627. IEEE Comput. Soc. Press, Los Alamitos (1992)"},{"key":"32_CR7","unstructured":"Wenceslas Fernandez de la Vega, On random 2-SAT (1992) (manuscript)"},{"key":"32_CR8","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: New worst-case upper bounds for MAX-2-SAT with an application to MAXCUT. Discrete Applied Mathematics (in press)"},{"issue":"3","key":"32_CR9","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1006\/jcss.1996.0081","volume":"53","author":"A. Goerdt","year":"1996","unstructured":"Goerdt, A.: A threshold for unsatisfiability. J. Comput. System Sci.\u00a053(3), 469\u2013486 (1996)","journal-title":"J. Comput. System Sci."},{"key":"32_CR10","unstructured":"Kulikov, A.S., Fedin, S.S.: Solution of the maximum cut problem in time 2|E|\/4, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov(POMI) 293, no. Teor. Slozhn. Vychisl. 7, 129\u2013138, 183 (2002)"},{"issue":"2","key":"32_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1013899527204","volume":"6","author":"M. Krivelevich","year":"2002","unstructured":"Krivelevich, M., Vu, V.H.: Approximating the independence number and the chromatic number in expected polynomial time. J. Comb. Optim.\u00a06(2), 143\u2013155 (2002)","journal-title":"J. Comb. Optim."},{"key":"32_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-36494-3_43","volume-title":"STACS 2003","author":"A. Taraz","year":"2003","unstructured":"Taraz, A., Coja-Oghlan, A.: Colouring random graphs in expected polynomial time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 487\u2013498. Springer, Heidelberg (2003)"},{"issue":"6","key":"32_CR13","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."}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,23]],"date-time":"2019-03-23T11:16:43Z","timestamp":1553339803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}