Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2020
Volume: 12290 LNCS
Page: 97-107
Language: English
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 6
Affiliated Colleges: