Advanced

Simple Iterative Heuristics for Correlation Clustering

Lingas, Andrzej LU and Persson, Mia (2014) 9th International Conference on Large-Scale Scientific Computations (LSSC) In Large-Scale Scientific Computing, LSSC 2013 8353. p.264-271
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 analyze the approximation and complexity aspects of this heuristic and its randomized variant where two clusters to merge are chosen uniformly at random among cluster pairs amenable to merge.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Large-Scale Scientific Computing, LSSC 2013
volume
8353
pages
264 - 271
publisher
Springer
conference name
9th International Conference on Large-Scale Scientific Computations (LSSC)
external identifiers
  • wos:000345642700029
  • scopus:84904093408
ISSN
0302-9743
1611-3349
DOI
10.1007/978-3-662-43880-0_29
language
English
LU publication?
yes
id
f9741ad7-7a03-41ef-8601-c2ac9ac45b10 (old id 4965771)
date added to LUP
2015-01-27 16:08:19
date last changed
2017-01-01 03:36:47
@inproceedings{f9741ad7-7a03-41ef-8601-c2ac9ac45b10,
  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 analyze the approximation and complexity aspects of this heuristic and its randomized variant where two clusters to merge are chosen uniformly at random among cluster pairs amenable to merge.},
  author       = {Lingas, Andrzej and Persson, Mia},
  booktitle    = {Large-Scale Scientific Computing, LSSC 2013},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {264--271},
  publisher    = {Springer},
  title        = {Simple Iterative Heuristics for Correlation Clustering},
  url          = {http://dx.doi.org/10.1007/978-3-662-43880-0_29},
  volume       = {8353},
  year         = {2014},
}