{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:23Z","timestamp":1740133943908,"version":"3.37.3"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Ltd","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12101594"],"award-info":[{"award-number":["12101594"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"crossref","award":["2021M693337"],"award-info":[{"award-number":["2021M693337"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871366"],"award-info":[{"award-number":["11871366"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013088","name":"Qing Lan Project","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100013088","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2017LA002"],"award-info":[{"award-number":["ZR2017LA002"]}],"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":["12131003"],"award-info":[{"award-number":["12131003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing Natural Science Foundation Project","award":["Z200002"],"award-info":[{"award-number":["Z200002"]}]},{"name":"Science and Technology Project of Hebei Education Department","award":["BJK2023076"],"award-info":[{"award-number":["BJK2023076"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"abstract":"<jats:p> Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label [Formula: see text]. Otherwise, this edge is marked by a negative label \u2212. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster\u2019s size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm. <\/jats:p>","DOI":"10.1142\/s0129054123410010","type":"journal-article","created":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T15:08:57Z","timestamp":1682608137000},"page":"1-18","source":"Crossref","is-referenced-by-count":0,"title":["An Improved Approximation Algorithm for the Capacitated Correlation Clustering Problem"],"prefix":"10.1142","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[{"name":"Institute of Mathematics, Hebei University of Technology, Tianjin 300401, P. R. China, jisai@hebut.edu.cn"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3638-3440","authenticated-orcid":false,"given":"Yukun","family":"Cheng","sequence":"additional","affiliation":[{"name":"School of Business, Suzhou University of Science and Technology, Suzhou 215009, P. R. China"}]},{"given":"Jingjing","family":"Tan","sequence":"additional","affiliation":[{"name":"School of Mathematics and Information Science, Weifang University, Weifang 261061, P. R. China"}]},{"given":"Zhongrui","family":"Zhao","sequence":"additional","affiliation":[{"name":"Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing 100124, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2023,4,27]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123410010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,27]],"date-time":"2023-04-27T15:09:06Z","timestamp":1682608146000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123410010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,27]]},"references-count":0,"alternative-id":["10.1142\/S0129054123410010"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123410010","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,4,27]]}}}