{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:47Z","timestamp":1725470747744},"publisher-location":"Berlin, Heidelberg","reference-count":21,"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_40","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"432-443","source":"Crossref","is-referenced-by-count":3,"title":["Approximating Almost All Instances of Max-Cut Within a Ratio Above the H\u00e5stad Threshold"],"prefix":"10.1007","author":[{"given":"A. C.","family":"Kaporis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. M.","family":"Kirousis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E. C.","family":"Stavropoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1287\/opre.36.3.493","volume":"36","author":"F. Barahona","year":"1988","unstructured":"Barahona, F., Grotschel, M., Junger, M., Reinelt, G.: An application of combinatorial optimization to statistical physics and circuit layout design. Operations Research\u00a036, 493\u2013513 (1988)","journal-title":"Operations Research"},{"key":"40_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/3-540-45687-2_9","volume-title":"Mathematical Foundations of Computer Science 2002","author":"M. Beis","year":"2002","unstructured":"Beis, M., Duckworth, W., Zito, M.: Packing edges in random regular graphs. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 118\u2013130. Springer, Heidelberg (2002)"},{"key":"40_CR3","unstructured":"Beis, M., Duckworth, W., Zito, M.: Large k-separated matchings of random regular graphs. In: Estivill-Castro, V. (ed.) ACSC, CRPIT, vol.\u00a038, pp. 175\u2013182. Australian Computer Society (2005)"},{"key":"40_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/BFb0024489","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Bertoni","year":"1997","unstructured":"Bertoni, A., Campadelli, P., Posenato, R.: Un upper bound for the maximum cut mean value. In: M\u00f6hring, R.H. (ed.) WG 1997. LNCS, vol.\u00a01335, pp. 78\u201384. Springer, Heidelberg (1997)"},{"key":"40_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: Proceedings of the 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA (2006)","DOI":"10.1145\/1132516.1132547"},{"key":"40_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45061-0_18","volume-title":"Automata, Languages and Programming","author":"A. Coja-Oghlan","year":"2003","unstructured":"Coja-Oghlan, A., Moore, C., Sanwalani, V.: Max k-cut and approximating the chromatic number of random graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 200\u2013211. Springer, Heidelberg (2003)"},{"issue":"4","key":"40_CR7","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1002\/rsa.20015","volume":"24","author":"D. Coppersmith","year":"2004","unstructured":"Coppersmith, D., Gamarnik, D., Hajiaghayi, M.T., Sorkin, G.B.: Random max sat, random max cut, and their phase transitions. Random Struct. Algorithms\u00a024(4), 502\u2013545 (2004)","journal-title":"Random Struct. Algorithms"},{"key":"40_CR8","unstructured":"de la Vega, W.F., Karpinski, M.: 9\/8-approximation algorithm for random max-3sat. Electronic Colloquium on Computational Complexity (ECCC)\u00a0(070) (2002)"},{"key":"40_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/11561071_21","volume-title":"Algorithms \u2013 ESA 2005","author":"J. D\u00edaz","year":"2005","unstructured":"D\u00edaz, J., Grammatikopoulos, G., Kaporis, A.C., Kirousis, L.M., P\u00e9rez, X., Sotiropoulos, D.G.: 5-regular graphs are 3-colorable with positive probability. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 215\u2013225. Springer, Heidelberg (2005)"},{"key":"40_CR10","unstructured":"Dubois, O., Mandler, J.: On the non-3-colourability of random graphs. ArXiv Mathematics e-prints (September 2002)"},{"issue":"1\u20132","key":"40_CR11","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A.M. Frieze","year":"1997","unstructured":"Frieze, A.M., McDiarmid, C.: Algorithmic theory of random graphs. Random Struct. Algorithms\u00a010(1\u20132), 5\u201342 (1997)","journal-title":"Random Struct. Algorithms"},{"key":"40_CR12","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"40_CR13","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048, 798\u2013869 (2001)","journal-title":"Journal of the ACM"},{"key":"40_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/11527695_14","volume-title":"Theory and Applications of Satisfiability Testing","author":"Y. Interian","year":"2005","unstructured":"Interian, Y.: Approximation algorithm for random MAX-k-SAT. In: Hoos, H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, pp. 173\u2013182. Springer, Heidelberg (2005)"},{"key":"40_CR15","unstructured":"Kalapala, V., Moore, C.: Max-cut on sparse random graphs. TR-CS-2002-24, University of New Mexico Department of Computer Science (2002)"},{"key":"40_CR16","first-page":"126","volume-title":"FOCS","author":"S. Khot","year":"2004","unstructured":"Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: FOCS, pp. 126\u2013135. IEEE Computer Society, Los Alamitos (2004)"},{"key":"40_CR17","unstructured":"Mitzenmacher, M.: Tight thresholds for the pure literal rule. Technical report, Digital Equipment Corporation (1997), available at: \n                    \n                      www.research.compaq.com\/SRC\/"},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1017\/S0963548300000596","volume":"2","author":"N.. Ngoc Van","year":"1993","unstructured":"Van Ngoc, N., Tuza, Z.: Linear-time algorithms for the max cut problem. Combinatorics, Probability & Computing\u00a02, 201\u2013210 (1993)","journal-title":"Combinatorics, Probability & Computing"},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0167-6377(94)90068-X","volume":"16","author":"S. Poljak","year":"1994","unstructured":"Poljak, S., Tuza, Z.: The expected relative error of the polyhedral approximation of the max-cut problem. Operations Research Letters\u00a016, 191\u2013198 (1994)","journal-title":"Operations Research Letters"},{"issue":"6","key":"40_CR20","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1137\/S0097539797328847","volume":"29","author":"L. Trevisan","year":"2000","unstructured":"Trevisan, L., Sorkin, G., Sudan, M., Williamson, D.: Gadgets, approximation, and linear programming. SIAM Journal on Computing\u00a029(6), 2074\u20132097 (2000)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"40_CR21","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C.: Differential equations for random processes and random graphs. The Annals of Applied Probability\u00a05(4), 1217\u20131235 (1995)","journal-title":"The Annals of Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:54Z","timestamp":1619507814000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11841036_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}