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.
| Original language | English |
|---|---|
| Pages (from-to) | 105-117 |
| Journal | International Journal of Metaheuristics |
| Volume | 3 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2014 |
Subject classification (UKÄ)
- Computer Science
Free keywords
- Randomised algorithms
- Time complexity
- Approximation algorithms
- Correlation clustering
- Graph clustering