Approximation algorithms for the capacitated correlation clustering problem with penalties

This paper considers the capacitated correlation clustering problem with penalties (CCorCwP), which is a new generalization of the correlation clustering problem. In this problem, we are given a complete graph, each edge is either positive or negative. Moreover, there is an upper bound on the number of vertices in each cluster, and each vertex has a penalty cost. The goal is to penalize some vertices and select a clustering of the remain vertices, so as to minimize the sum of the number of positive cut edges, the number of negative non-cut edges and the penalty costs. In this paper we present an integer programming, linear programming relaxation and two polynomial time algorithms for the CCorCwP. Given parameter $$\delta \in (0,4/9]$$ δ ∈ ( 0 , 4 / 9 ] , the first algorithm is a $$\left( 8/(4-5\delta ), 8/\delta \right) $$ 8 / ( 4 - 5 δ ) , 8 / δ -bi-criteria approximation algorithm for the CCorCPwP, which means that the number of vertices in each cluster does not exceed $$8/(4-5\delta )$$ 8 / ( 4 - 5 δ ) times the upper bound, and the output objective function value of the algorithm does not exceed $$8/\delta $$ 8 / δ times the optimal value. The second one is based on above bi-criteria approximation, and we prove that the second algorithm can achieve a constant approximation ratio for some special instances of the CCorCwP.