{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T19:35:30Z","timestamp":1725478530524},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540695134"},{"type":"electronic","value":"9783540695141"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/11970125_16","type":"book-chapter","created":{"date-parts":[[2007,1,24]],"date-time":"2007-01-24T05:47:40Z","timestamp":1169617660000},"page":"202-213","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Maximum Cut with Limited Unbalance"],"prefix":"10.1007","author":[{"given":"Giulia","family":"Galbiati","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/3-540-48777-8_2","volume-title":"Integer Programming and Combinatorial Optimization","author":"A.A. Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.I.: Approximation algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol.\u00a01610, pp. 17\u201330. Springer, Heidelberg (1999)"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0166-218X(81)90001-9","volume":"3","author":"J. Akiyama","year":"1981","unstructured":"Akiyama, J., Avis, D., Chvatal, V., Era, H.: Balancing signed graphs. Discrete Applied Mathematics\u00a03, 227\u2013233 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F. Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optimization\u00a05, 13\u201351 (1995)","journal-title":"SIAM J. Optimization"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM\u00a045, 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1006\/jagm.2001.1183","volume":"41","author":"U. Feige","year":"2001","unstructured":"Feige, U., Langberg, M.: Approximation algorithms for maximization problems in graph partitioning. J. of Algorithms\u00a041, 1074\u20131211 (2001)","journal-title":"J. of Algorithms"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica\u00a018, 67\u201381 (1997)","journal-title":"Algorithmica"},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of ACM"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11561071_19","volume-title":"Algorithms \u2013 ESA 2005","author":"A. Hayrapetyan","year":"2005","unstructured":"Hayrapetyan, A., Kempe, D., Pal, M., Svitkina, Z.: Unbalanced Graph Cuts. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 191\u2013202. Springer, Heidelberg (2005)"},{"key":"16_CR9","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":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11841036_40","volume-title":"Algorithms \u2013 ESA 2006","author":"A.C. Kaporis","year":"2006","unstructured":"Kaporis, A.C., Kirousis, L.M., Stavropoulos, E.C.: Approximating Almost All Instances of MAX-CUT Within a Ratio Above the H\u00e5stad Threshold. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"key":"16_CR11","series-title":"AMS - DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/dimacs\/020\/04","volume-title":"Combinatorial Optimization","author":"S. Poljak","year":"1995","unstructured":"Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs. In: Cook, W., Lovasz, L., Seymour, P. (eds.) Combinatorial Optimization. AMS - DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a020, pp. 181\u2013244. American Mathematical Society, Providence (1995)"},{"issue":"6","key":"16_CR12","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"},{"key":"16_CR13","unstructured":"Vazirani, V.V.: Approximation Algorithms, ch. 26. Springer, Heidelberg (2001)"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y. Ye","year":"2001","unstructured":"Ye, Y.: A.699-approximation algorithm for Max-Bisection. Math. Programming Ser. A\u00a090, 101\u2013111 (2001)","journal-title":"Math. Programming Ser. A"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11970125_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:23:49Z","timestamp":1619508229000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11970125_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540695134","9783540695141"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11970125_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}