Indexed by:
Abstract:
Correlation clustering problem is a classical clustering problem and has many applications in protein interaction networks, cross-lingual link detection, communication networks, etc. In this paper, we discuss the capacitated correlation clustering problem on labeled complete graphs, in which each edge is labeled + or - to indicate two endpoints are "similar" or "dissimilar", respectively. Our objective is to partition the vertex set into several clusters, subject to an upper bound on cluster size, 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. The main contribution of this work is providing a 5.37-approximation algorithm for the capacitated correlation clustering problem, improving the current best approximation ratio of 6 [21]. In addition, we have conducted a series of numerical experiments, which effectively demonstrate the effectiveness of our algorithm.
Keyword:
Reprint Author's Address:
Email:
Source :
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021
ISSN: 0302-9743
Year: 2021
Volume: 13135
Page: 35-45
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: