Indexed by:
Abstract:
Correlation clustering problem is an elegant clustering problem and has many applications in protein interaction networks, cross-lingual link detection, etc. In this paper, we introduce the capacitated correlation clustering problem with penalties by combining the capacitated correlation clustering problem and the correlation problem with penalties. There are two main contributions in this paper. The first one is that we give an integer programming for the capacitated correlation clustering problem with penalties. The second one is that we provide an LP-based (4 / (4 - 5 α), 8 / α) -bi-criteria approximation algorithm for this problem, where parameter α∈ (0, 4 / 9 ]. © 2021, Springer Nature Switzerland AG.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 13153 LNCS
Page: 15-26
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: 3
Affiliated Colleges: