Indexed by:
Abstract:
This paper considers the correlation clustering problem with non-uniform hard constrained cluster sizes, which is a generalization of correlation clustering problem. In this problem, we are given a positive integer U-upsilon for each vertex upsilon, and require vertical bar C vertical bar = min(upsilon is an element of C) U-upsilon for any cluster C. We provide a (2, 4)-bicriteria approximation algorithm for this problem. Namely, the solution returned by the algorithm has the cost that is at most 4 times the optimum, and for each cluster C in the solution, we have vertical bar C vertical bar <= 2min(upsilon is an element of C) U-upsilon.
Keyword:
Reprint Author's Address:
Email:
Source :
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019
ISSN: 0302-9743
Year: 2019
Volume: 11640
Page: 159-168
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: