Indexed by:
Abstract:
Lower bounded correlation clustering problem (LBCorCP) is a new generalization of the correlation clustering problem (CorCP). In the LBCorCP, we are given an integer L and a complete labelled graph. Each edge in the graph is either positive or negative based on the similarity of its two endpoints. The goal is to find a clustering of the vertices, each cluster contains at least L vertices, so as to minimize the sum of the number of positive cut edges and negative uncut edges. In this paper, we first introduce the LBCorCP and give three algorithms for this problem. The first algorithm is a random algorithm, which is designed for the instances of the LBCorCP with fewer positive edges. The second one is that we let the set V itself as a cluster and prove that the algorithm works well on two specially instances with fewer negative edges. The last one is an LP-rounding based iterative algorithm, which is also provided for the instances with fewer negative edges. The above three algorithms can quickly solve some special instances in polynomial time and obtain a smaller approximation ratio. In addition, we conduct simulations to evaluate the performance of our algorithms.
Keyword:
Reprint Author's Address:
Email:
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:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: