Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Simple Iterative Heuristics for Correlation Clustering

Lingas, Andrzej LU and Persson, Mia (2014) 9th International Conference on Large-Scale Scientific Computations (LSSC) 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
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Large-Scale Scientific Computing, LSSC 2013
volume
8353
pages
264 - 271
publisher
Springer
conference name
9th International Conference on Large-Scale Scientific Computations (LSSC)
conference dates
2013-06-03 - 2013-06-07
external identifiers
  • wos:000345642700029
  • scopus:84904093408
ISSN
1611-3349
0302-9743
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
2016-04-01 10:27:44
date last changed
2024-01-06 17:21:14
@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         = {{1611-3349}},
  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}},
  doi          = {{10.1007/978-3-662-43880-0_29}},
  volume       = {{8353}},
  year         = {{2014}},
}