收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址: