Approximation algorithms for the capacitated correlation clustering problem with penalties

Sai Ji (), Gaidi Li (), Dongmei Zhang () and Xianzhao Zhang ()
Additional contact information
Sai Ji: Hebei University of Technology
Gaidi Li: Beijing University of Technology
Dongmei Zhang: Shandong Jianzhu University
Xianzhao Zhang: Linyi University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 1, No 4, 16 pages

Abstract: 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 \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.

Keywords: Correlation clustering; Capacitated; Penalties; Approximation algorithm; LP-rounding (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00930-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:45:y:2023:i:1:d:10.1007_s10878-022-00930-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00930-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().