Title: Iterative merging heuristics for correlation clustering

Authors: Andrzej Lingas; Mia Persson; Dzmitry Sledneu

Addresses: Department of Computer Science, Lund University, Sweden ' Department of Computer Science, Malmö University, Sweden ' Centre for Mathematical Sciences, Lund University, Sweden

Abstract: A straightforward natural iterative heuristic for correlation clustering in the general setting is to start from singleton clusters and whenever merging two clusters improves the current quality score merge them into a single cluster. We analyse the approximation and complexity aspects of this heuristic and its three simple deterministic or random refinements.

Keywords: graph clustering; correlation clustering; approximation algorithms; randomised algorithms; time complexity; iterative heuristics.

DOI: 10.1504/IJMHEUR.2014.063141

International Journal of Metaheuristics, 2014 Vol.3 No.2, pp.105 - 117

Received: 05 Oct 2013
Accepted: 28 Mar 2014
Published online: 25 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article