Approximation Algorithm for the Correlation Clustering Problem with Non-uniform Hard Constrained Cluster Sizes

摘要

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_v for each vertex v, and require |C| ≤ min_(v∈C) U_v 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 |C| ≤ 2 min_(v∈C)U_v.