收录:
摘要:
In this paper, we consider the balanced 2-correlation clustering problem on well-proportional graphs, which has applications in protein interaction networks, cross-lingual link detection, communication networks, among many others. Given a complete graph G=(V,E) with each edge (u,v)\in E labeled by + or −, the goal is to partition the vertices into two clusters of equal size to minimize the number of positive edges whose endpoints lie in different clusters plus the number of negative edges whose endpoints lie in the same cluster. We provide a (Formula Presented)-balanced approximation algorithm for the balanced 2-correlation clustering problem on M-proportional graphs. Namely, the cost of the vertex partition (Formula Presented) returned by the algorithm is at most (Formula Presented) times the optimum solution, and (Formula Presented). © 2020, Springer Nature Switzerland AG.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
ISSN: 0302-9743
年份: 2020
卷: 12290 LNCS
页码: 97-107
语种: 英文
归属院系: