{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:33:54Z","timestamp":1758710034408},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,19]],"date-time":"2015-04-19T00:00:00Z","timestamp":1429401600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["11371001"],"award-info":[{"award-number":["11371001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSF of China","doi-asserted-by":"crossref","award":["11071268"],"award-info":[{"award-number":["11071268"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10878-015-9880-z","type":"journal-article","created":{"date-parts":[[2015,4,18]],"date-time":"2015-04-18T05:57:33Z","timestamp":1429336653000},"page":"1017-1035","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding"],"prefix":"10.1007","volume":"32","author":[{"given":"Chenchen","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenqing","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,19]]},"reference":[{"key":"9880_CR1","doi-asserted-by":"crossref","unstructured":"Andersson G (1999) An approximation algorithm for Max $$p$$ p -Section. In: 16th Annual Symposium on Theoretical Aspects of Computer Science. Springer Press, Trier, pp 237\u2013247","DOI":"10.1007\/3-540-49116-3_22"},{"key":"9880_CR2","doi-asserted-by":"crossref","unstructured":"Austrin P, Benabbas S, Georgiou K (2013) Better balance by being biased: A 0.8776-approximation for Max Bisection. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM Press, New Orleans, pp 277\u2013294","DOI":"10.1137\/1.9781611973105.21"},{"key":"9880_CR3","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/02331934.2011.592527","volume":"61","author":"S Choudhury","year":"2012","unstructured":"Choudhury S, Gaur D, Krishnamurti R (2012) An approximation algorithm for Max $$k$$ k -Uncut with capacity constraints. Optimization 61:143\u2013150","journal-title":"Optimization"},{"key":"9880_CR4","unstructured":"Doids Y, Guruswami V, Khanna S (1999) The 2-catalog segmentation problem. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM Press, Baltimore, pp 897\u2013898"},{"key":"9880_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.11.003","volume":"60","author":"U Feige","year":"2006","unstructured":"Feige U, Langberg M (2006) The $${\\rm RPR}^{2}$$ RPR 2 rounding technique for semidefinite programs. J Algorithms 60:1\u201323","journal-title":"J Algorithms"},{"key":"9880_CR6","doi-asserted-by":"crossref","first-page":"S170","DOI":"10.1287\/opre.40.1.S170","volume":"40","author":"T Feo","year":"1992","unstructured":"Feo T, Goldschmidt O, Khellaf M (1992) One-half approximation algorithms for the $$k$$ k -partition problem. Oper Res 40:S170\u2013S173","journal-title":"Oper Res"},{"key":"9880_CR7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"AM Frieze","year":"1997","unstructured":"Frieze AM, Jerrum M (1997) Improved approximation algorithms for MAX $$k$$ k -CUT and MAX BISECTION. Algorithmica 18:67\u201381","journal-title":"Algorithmica"},{"key":"9880_CR8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42:1115\u20131145","journal-title":"J ACM"},{"key":"9880_CR9","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1016\/j.jcss.2003.07.012","volume":"68","author":"MX Goemans","year":"2004","unstructured":"Goemans MX, Williamson DP (2004) Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. J Comput Syst Sci 68:442\u2013470","journal-title":"J Comput Syst Sci"},{"key":"9880_CR10","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1002\/rsa.10035","volume":"20","author":"E Halperin","year":"2002","unstructured":"Halperin E, Zwick U (2002) A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Struct Algorithms 20:382\u2013402","journal-title":"Random Struct Algorithms"},{"key":"9880_CR11","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/s101070100288","volume":"92","author":"Q Han","year":"2002","unstructured":"Han Q, Ye Y, Zhang J (2002) An improved rounding method and semidefinite programming relaxation for graph partition. Math Progr Ser B 92:509\u2013535","journal-title":"Math Progr Ser B"},{"key":"9880_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/972639.972644","volume":"51","author":"J Kleinberg","year":"2004","unstructured":"Kleinberg J, Papadimitriou C, Raghavan P (2004) Segmentation problems. J ACM 51:1\u201316","journal-title":"J ACM"},{"key":"9880_CR13","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1137\/S1052623400380079","volume":"12","author":"JB Lasserre","year":"2002","unstructured":"Lasserre JB (2002) An explicit equivalent positive semidefinite program for nonlinear 0\u20131 programs. SIAM J Optim 12:756\u2013769","journal-title":"SIAM J Optim"},{"key":"9880_CR14","doi-asserted-by":"crossref","unstructured":"Ling A (2009) Approximation algorithms for Max 3-Section using complex semidefinite programming relaxation. In: 3rd International Conference on Combinatorial Optimization and Applications. Springer Press, Huangshan, pp 219\u2013230","DOI":"10.1007\/978-3-642-02026-1_20"},{"key":"9880_CR15","doi-asserted-by":"crossref","unstructured":"Raghavendra P, Tan N (2012) Approximating CSPs with global cardinality constraints using SDP hierarchies. In: 23rd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM Press, Kyoto, pp 373\u2013387","DOI":"10.1137\/1.9781611973099.33"},{"key":"9880_CR16","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23:555\u2013565","journal-title":"J ACM"},{"key":"9880_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/s10878-013-9673-1","volume":"29","author":"C Wu","year":"2015","unstructured":"Wu C, Du D, Xu D (2015) An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems. J Comb Optim 29:53\u201366","journal-title":"J Comb Optim"},{"key":"9880_CR18","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1023\/A:1026094110647","volume":"27","author":"D Xu","year":"2003","unstructured":"Xu D, Han J, Huang Z, Zhang L (2003) Improved approximation algorithms for MAX $$n\/2$$ n \/ 2 -DIRECTED-BISECTION and MAX $$n\/2$$ n \/ 2 -DENSE-SUBGRAPH. J Glob Optim 27:399\u2013410","journal-title":"J Glob Optim"},{"key":"9880_CR19","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y Ye","year":"2001","unstructured":"Ye Y (2001) A.699-approximation algorithm for Max-Bisection. Math Program 90:101\u2013111","journal-title":"Math Program"},{"key":"9880_CR20","doi-asserted-by":"crossref","first-page":"871","DOI":"10.1137\/04061341X","volume":"16","author":"S Zhang","year":"2006","unstructured":"Zhang S, Huang Y (2006) Complex quadratic optimization and semidefinite programming. SIAM J Optim 16:871\u2013890","journal-title":"SIAM J Optim"},{"key":"9880_CR21","doi-asserted-by":"crossref","unstructured":"Zwick U (1999) Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems. In: 31st Annual ACM Symposium on Theory of Computing. ACM Press, Atlanta, pp 679\u2013687","DOI":"10.1145\/301250.301431"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9880-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9880-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9880-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9880-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T04:01:26Z","timestamp":1589515286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9880-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,19]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9880"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9880-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,19]]}}}