Approximation algorithms for the lower bounded correlation clustering problem

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.

Automated summary

This paper introduces a new generalization of the correlation clustering problem called the lower bounded correlation clustering problem (LBCorCP). Three algorithms are proposed to solve this problem. The first algorithm is a random algorithm for instances with fewer positive edges. The second algorithm treats the set V itself as a cluster and works well on instances with fewer negative edges. The last algorithm is an LP-rounding based iterative algorithm for instances with fewer negative edges. Simulations are conducted to evaluate the performance of the algorithms.