{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T07:09:15Z","timestamp":1750748955377,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T00:00:00Z","timestamp":1592956800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T00:00:00Z","timestamp":1592956800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2019MA032"],"award-info":[{"award-number":["ZR2019MA032"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61433012"],"award-info":[{"award-number":["61433012"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10878-020-00612-1","type":"journal-article","created":{"date-parts":[[2020,6,24]],"date-time":"2020-06-24T22:02:31Z","timestamp":1593036151000},"page":"933-952","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation algorithms for two variants of correlation clustering problem"],"prefix":"10.1007","volume":"43","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2784-5073","authenticated-orcid":false,"given":"Min","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,24]]},"reference":[{"key":"612_CR1","unstructured":"Amit N (2004) The bicluster graph editing problem. Diss, Tel Aviv University"},{"issue":"5","key":"612_CR2","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/110848712","volume":"41","author":"N Ailon","year":"2012","unstructured":"Ailon N, Avigdor-Elgrabli N, Liberty E, Zuylen AV (2012) Improved approximation algorithms for bipartite correlation clustering. SIAM J Comput 41(5):1110\u20131121","journal-title":"SIAM J Comput"},{"issue":"3","key":"612_CR3","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1002\/sam.10012","volume":"1","author":"E Achtert","year":"2010","unstructured":"Achtert E, B\u00f6hm C, David J, Kr\u00f6ger P, Zimek A (2010) Global correlation clustering based on the hough transform. Stat Anal Data Min 1(3):111\u2013127","journal-title":"Stat Anal Data Min"},{"key":"612_CR4","unstructured":"Ahn K J, Cormode G, Guha S, Mcgregor A, Wirth A (2015) Correlation clustering in data streams. In: Proceedings of the 32th International Conference on International Conference on Machine Learning (ICML), pp 2237-2246"},{"issue":"5","key":"612_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: ranking and clustering. J ACM 55(5):1\u201327 Article No. 23","journal-title":"J ACM"},{"key":"612_CR6","unstructured":"Arthur D, Vassilvitskii S (2007) k-Means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1027-1035"},{"issue":"1\u20132","key":"612_CR7","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10107-012-0565-4","volume":"141","author":"A Aggarwal","year":"2013","unstructured":"Aggarwal A, Louis A, Bansal M, Garg N, Gupta N, Gupta S, Jain S (2013) A 3-approximation algorithm for the facility location problem with uniform capacities. Math Program 141(1\u20132):527\u2013547","journal-title":"Math Program"},{"key":"612_CR8","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2017) Better guarantees for $$k$$-means and euclidean $$k$$-median by primal-dual algorithms. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pp 61-72","DOI":"10.1109\/FOCS.2017.15"},{"issue":"2","key":"612_CR9","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ejor.2014.10.011","volume":"242","author":"K Aardal","year":"2015","unstructured":"Aardal K, van den Berg PL, Gijswijt D, Li S (2015) Approximation algorithms for hard capacitated k-facility location problems. Eur J Oper Res 242(2):358\u2013368","journal-title":"Eur J Oper Res"},{"issue":"1","key":"612_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-012-0522-9","volume":"35","author":"F Bonchi","year":"2013","unstructured":"Bonchi F (2013) Overlapping correlation clustering. Knowl Inf Syst 35(1):1\u201332","journal-title":"Knowl Inf Syst"},{"issue":"1\u20133","key":"612_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal N, Blum A, Chawla S (2004) Correlation clustering. Mach learn 56(1\u20133):89\u2013113","journal-title":"Mach learn"},{"key":"612_CR12","doi-asserted-by":"crossref","unstructured":"Byrka J, Fleszar K, Rybicki B, Spoerhase J (2015) Bi-factor approximation algorithms for hard capacitated $$k$$-median problems. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 722-736","DOI":"10.1137\/1.9781611973730.49"},{"key":"612_CR13","doi-asserted-by":"crossref","unstructured":"Braverman V, Lang H, Levin K, Monemizadeh M (2016) Clustering problems on sliding windows. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1374-1390","DOI":"10.1137\/1.9781611974331.ch95"},{"issue":"4","key":"612_CR14","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1145\/3186728.3164143","volume":"11","author":"M Ceccarello","year":"2017","unstructured":"Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, Vandin F (2017) Clustering uncertain graphs. Proc VLDB Endow 11(4):472\u2013484","journal-title":"Proc VLDB Endow"},{"issue":"3","key":"612_CR15","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guruswami V, Wirth A (2005) Clustering with qualitative information. J Comp Syst Sci 71(3):360\u2013383","journal-title":"J Comp Syst Sci"},{"key":"612_CR16","doi-asserted-by":"crossref","unstructured":"Chawla S, Makarychev K, Schramm T, Yaroslavtsev G (2015) Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In: Proceedings of the 47th annual ACM symposium on Theory of computing (STOC), pp 219-228","DOI":"10.1145\/2746539.2746604"},{"issue":"2","key":"612_CR17","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"E Demaine","year":"2006","unstructured":"Demaine E, Emanuel D, Fiat A, Immorlica N (2006) Correlation clustering in general weighted graphs. Theor Comp Sci 361(2):172\u2013187","journal-title":"Theor Comp Sci"},{"issue":"1","key":"612_CR18","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze A, Jerrum M (1997) Improved approximation algorithms for maxk-cut and max bisection. Algorithmica 18(1):67\u201381","journal-title":"Algorithmica"},{"key":"612_CR19","doi-asserted-by":"crossref","unstructured":"Giotis I, Guruswami V (2006) Correlation clustering with a fixed number of clusters. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1167-1176","DOI":"10.1145\/1109557.1109686"},{"issue":"6","key":"612_CR20","doi-asserted-by":"publisher","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(6):1115\u20131145","journal-title":"J ACM"},{"issue":"5","key":"612_CR21","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1109\/TKDE.2013.123","volume":"26","author":"Y Gu","year":"2013","unstructured":"Gu Y, Gao C, Cong G, Yu G (2013) Effective and efficient clustering methods for correlated probabilistic graphs. IEEE Trans Knowl Data Eng 26(5):1117\u20131130","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"2","key":"612_CR22","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1109\/TKDE.2011.243","volume":"25","author":"G Kollios","year":"2011","unstructured":"Kollios G, Potamias M, Terzi E (2011) Clustering large probabilistic graphs. IEEE Trans Knowl Data Eng 25(2):325\u2013336","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"2","key":"612_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2983633","volume":"13","author":"S Li","year":"2017","unstructured":"Li S (2017) On uniform capacitated $$k$$-median beyond the natural LP relaxation. ACM Trans Algorithms 13(2):1\u201318 Article No. 22","journal-title":"ACM Trans Algorithms"},{"key":"612_CR24","doi-asserted-by":"crossref","unstructured":"Li M, Xu D, Zhang D, Zhang T (2019) A streaming algorithm for $$k$$-Means with approximate coreset. Asia Pac J Oper Res 36:1950006:1\u20131950006:18","DOI":"10.1142\/S0217595919500064"},{"key":"612_CR25","doi-asserted-by":"crossref","unstructured":"Mathieu C, Schudy W (2010) Correlation clustering with noisy input. In: Proceedings of the 21th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 712-728","DOI":"10.1137\/1.9781611973075.58"},{"issue":"2","key":"612_CR26","first-page":"211","volume":"21","author":"C Mathieu","year":"2010","unstructured":"Mathieu C, Sankur O, Schudy W (2010) Online correlation clustering. Comput Stat 21(2):211\u2013229","journal-title":"Comput Stat"},{"issue":"3","key":"612_CR27","doi-asserted-by":"publisher","first-page":"036104","DOI":"10.1103\/PhysRevE.74.036104","volume":"74","author":"MEJ Newman","year":"2006","unstructured":"Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104","journal-title":"Phys Rev E"},{"issue":"3","key":"612_CR28","doi-asserted-by":"publisher","first-page":"1857","DOI":"10.1137\/140994198","volume":"25","author":"GJ Puleo","year":"2015","unstructured":"Puleo GJ, Milenkovic O (2015) Correlation clustering with constrained cluster sizes and extended weights bounds. SIAM J Optim 25(3):1857\u20131872","journal-title":"SIAM J Optim"},{"issue":"6","key":"612_CR29","doi-asserted-by":"publisher","first-page":"4105","DOI":"10.1109\/TIT.2018.2819696","volume":"64","author":"GJ Puleo","year":"2018","unstructured":"Puleo GJ, Milenkovic O (2018) Correlation clustering and biclustering with locally bounded errors. IEEE Trans Inf Theory 64(6):4105\u20134119","journal-title":"IEEE Trans Inf Theory"},{"key":"612_CR30","doi-asserted-by":"crossref","unstructured":"Pal M, Tardos T, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp 329-338","DOI":"10.1109\/SFCS.2001.959907"},{"key":"612_CR31","unstructured":"Swamy C (2004) Correlation clustering: Maximizing agreements via semidefinite programming. In: Proceedings of the 15th Annual ACM-SIAM symposium on Discrete Algorithms (SODA), pp 526-527"},{"issue":"3","key":"612_CR32","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1287\/moor.1090.0385","volume":"34","author":"ZDP Williamson","year":"2009","unstructured":"Williamson ZDP (2009) Deterministic pivoting algorithms for constrained ranking and clustering problems. Math Oper Res 34(3):594\u2013620","journal-title":"Math Oper Res"},{"key":"612_CR33","doi-asserted-by":"crossref","unstructured":"Zhang C, Yarkony J, Hamprecht F A (2014) Cell detection and segmentation using correlation clustering. In: Proceedings of the 17th International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI), pp 9-16","DOI":"10.1007\/978-3-319-10404-1_2"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00612-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00612-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00612-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T17:53:17Z","timestamp":1657734797000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00612-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,24]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["612"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00612-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,6,24]]},"assertion":[{"value":"24 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}