Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Iterative merging heuristics for correlation clustering

Lingas, Andrzej LU ; Persson, Mia and Sledneu, Dzmitry LU (2014) In International Journal of Metaheuristics 3(2). p.105-117
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.
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Randomised algorithms, Time complexity, Approximation algorithms, Correlation clustering, Graph clustering
in
International Journal of Metaheuristics
volume
3
issue
2
pages
105 - 117
publisher
Inderscience Publishers
ISSN
1755-2184
DOI
10.1504/IJMHEUR.2014.063141
language
English
LU publication?
yes
id
fa9b965a-9d7f-413b-831c-801fe874d10d (old id 7866164)
date added to LUP
2016-04-01 10:57:06
date last changed
2018-11-21 19:53:05
@article{fa9b965a-9d7f-413b-831c-801fe874d10d,
  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.}},
  author       = {{Lingas, Andrzej and Persson, Mia and Sledneu, Dzmitry}},
  issn         = {{1755-2184}},
  keywords     = {{Randomised algorithms; Time complexity; Approximation algorithms; Correlation clustering; Graph clustering}},
  language     = {{eng}},
  number       = {{2}},
  pages        = {{105--117}},
  publisher    = {{Inderscience Publishers}},
  series       = {{International Journal of Metaheuristics}},
  title        = {{Iterative merging heuristics for correlation clustering}},
  url          = {{http://dx.doi.org/10.1504/IJMHEUR.2014.063141}},
  doi          = {{10.1504/IJMHEUR.2014.063141}},
  volume       = {{3}},
  year         = {{2014}},
}