Journal Article

Approximation algorithms for the lower bounded correlation clustering problem

Dong, Yinhong, Ji, Sai, Du, Donglei, Xu, Dachuan, Wang, Dongzhao

2023

Overview

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.

• Publisher: Springer US,Springer Nature B.V
• Subject: Algorithms / Apexes / Approximation / Clustering / Combinatorics / Convex and Discrete Geometry / Correlation / Integer programming / Iterative algorithms / Mathematical Modeling and Industrial Mathematics / Mathematics / Mathematics and Statistics / Operations Research/Decision Theory / Optimization / Polynomials / Theory of Computation