Simple Iterative Heuristics for Correlation Clustering
(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:
https://lup.lub.lu.se/record/4965771
- author
- Lingas, Andrzej LU and Persson, Mia
- organization
- publishing date
- 2014
- 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
- 2025-01-14 15:25:07
@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}}, }