RT Journal Article
A1 Sai Ji,Dachuan Xu,Donglei Du,Ling Gai,Zhongrui Zhao;
AD Department of Operations Research and Information Engineering, 中国 ; 科学与工程计算研究所, 中国 ; 工商管理学院, 加拿大 ; 旭日工商管理学院, 中国 ; Department of Operations Research and Information Engineering, 中国
T1 Approximation Algorithm for the Balanced 2-Correlation Clustering Problem
YR 2022
IS 5
vo 27
OP 777-OP 784
K1 approximation algorithm;balanced clustering;k-correlation clustering;positive edge dominant graphs
AB The Correlation Clustering Problem (CorCP) is a significant clustering problem based on the similarity of data. It has significant applications in different fields, such as machine learning, biology, and data mining, and many different problems in other areas. In this paper, the Balanced 2-CorCP (B 2-CorCP) is introduced and examined, and a new interesting variant of the CorCP is described. The goal of this clustering problem is to partition the vertex set into two clusters with equal size, such that the number of disagreements is minimized. We first present a polynomial time algorithm for the B 2-CorCP on M-positive edge dominant graphs (M⩾3). Then, we provide a series of numerical experiments, and the results show the effectiveness of our algorithm.
SN 1007-0214
LA EN