Iterative merging heuristics for correlation clustering

Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)105-117
JournalInternational Journal of Metaheuristics
Volume3
Issue number2
DOIs
Publication statusPublished - 2014

Subject classification (UKÄ)

  • Computer Science

Keywords

  • Randomised algorithms
  • Time complexity
  • Approximation algorithms
  • Correlation clustering
  • Graph clustering

Fingerprint

Dive into the research topics of 'Iterative merging heuristics for correlation clustering'. Together they form a unique fingerprint.

Cite this