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.
International Journal of Metaheuristics, 2014 Vol.3 No.2, pp.105 - 117
Received: 05 Oct 2013
Accepted: 28 Mar 2014
Published online: 03 Jul 2014 *