{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T23:40:35Z","timestamp":1687563635501},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,6,29]],"date-time":"2012-06-29T00:00:00Z","timestamp":1340928000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s10878-012-9526-3","type":"journal-article","created":{"date-parts":[[2012,6,28]],"date-time":"2012-06-28T15:07:42Z","timestamp":1340896062000},"page":"315-327","source":"Crossref","is-referenced-by-count":4,"title":["Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems"],"prefix":"10.1007","volume":"27","author":[{"given":"Zi","family":"Xu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,6,29]]},"reference":[{"key":"9526_CR1","first-page":"378","volume-title":"Proceedings of SODA","author":"Y Dodis","year":"1999","unstructured":"Dodis Y, Guruswami V, Khanna S (1999) The 2-catalog segmentation problem. In: Proceedings of SODA, pp 378\u2013380"},{"key":"9526_CR2","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 RPR2 rounding technique for semidefinite programs. J Algorithms 60:1\u201323","journal-title":"J Algorithms"},{"key":"9526_CR3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze A, Jerrum M (1997) Improved approximation algorithms for max k-cut and max-bisection. Algorithmica 18:67\u201381","journal-title":"Algorithmica"},{"key":"9526_CR4","first-page":"321","volume-title":"Proceedings of ICS","author":"V Guruswami","year":"2011","unstructured":"Guruswami V, Makarychev Y, Raghavendra P, Steurer D, Zhou Y (2011) Finding almost-perfect graph bisections. In: Proceedings of ICS, pp 321\u2013337"},{"key":"9526_CR5","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":"9526_CR6","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":"9526_CR7","first-page":"473","volume-title":"Proceedings of STOC","author":"J Kleinberg","year":"1998","unstructured":"Kleinberg J, Papadimitriou C, Raghavan P (1998) Segmentation problems. In: Proceedings of STOC, pp 473\u2013482"},{"key":"9526_CR8","first-page":"373","volume-title":"Proceedings of SODA","author":"P Raghavendra","year":"2012","unstructured":"Raghavendra P, Tan N (2012) Approximating CSPs with global cardinality constraints using SDP hierarchies. In: Proceedings of SODA, pp 373\u2013387"},{"key":"9526_CR9","first-page":"447","volume-title":"Proceedings of FSTTCS","author":"R Saket","year":"2010","unstructured":"Saket R (2010) Quasi-random PCP and hardness of 2-catalog segmentation. In: Proceedings of FSTTCS, pp 447\u2013458"},{"key":"9526_CR10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.3934\/jimo.2012.8.117","volume":"8","author":"C Wu","year":"2012","unstructured":"Wu C, Xu D, Zhao X (2012) An improved approximation algorithm for the 2-catalog segmentation problem using semidefinite programming relaxation. J Ind Manag Optim 8:117\u2013126","journal-title":"J Ind Manag Optim"},{"key":"9526_CR11","first-page":"357","volume":"21","author":"D Xu","year":"2003","unstructured":"Xu D, Han J (2003) Approximation algorithm for max-bisection problem with the positive semidefinite relaxation. J Comput Math 21:357\u2013366","journal-title":"J Comput Math"},{"key":"9526_CR12","unstructured":"Xu D, Ye Y, Zhang J (2002) A note on approximating the 2-catalog segmentation problem. Working Paper, Department of Management Sciences, Henry, B Tippie College of Business, The University of Iowa, Iowa City, IA, 52242, USA"},{"key":"9526_CR13","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1080\/10556780310001634082","volume":"18","author":"D Xu","year":"2003","unstructured":"Xu D, Ye Y, Zhang J (2003) Approximating the 2-catalog segmentation problem using semidefinite programming relaxations. Optim Methods Softw 18:705\u2013719","journal-title":"Optim Methods Softw"},{"key":"9526_CR14","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/PL00011415","volume":"90","author":"Y Ye","year":"2001","unstructured":"Ye Y (2001) A 0.699-approximation algorithm for max-bisection. Math Program 90:101\u2013111","journal-title":"Math Program"},{"key":"9526_CR15","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1145\/301250.301431","volume-title":"Proceedings of STOC","author":"U Zwick","year":"1999","unstructured":"Zwick U (1999) Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceedings of STOC, pp 679\u2013687"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9526-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-012-9526-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-012-9526-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T23:24:43Z","timestamp":1687562683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-012-9526-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,29]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9526"],"URL":"https:\/\/doi.org\/10.1007\/s10878-012-9526-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,6,29]]}}}