Indexed by:
Abstract:
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 is an element of (0, 4/9], the first algorithm is a (8/(4 - 5 delta), 8/delta)-N-criteria approximation algorithm for the CCorCPwP, which means that the number of vertices in each cluster does not exceed 8/(4 - 5 delta) times the upper bound, and the output objective function value of the algorithm does not exceed 8/delta 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.
Keyword:
Reprint Author's Address:
Source :
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN: 1382-6905
Year: 2023
Issue: 1
Volume: 45
1 . 0 0 0
JCR@2022
ESI Discipline: MATHEMATICS;
ESI HC Threshold:9
Cited Count:
WoS CC Cited Count: 3
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 7
Affiliated Colleges: