A local-search 2-approximation for 2-correlation-clustering

Tom Coleman, James Saunderson, Anthony Wirth

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

18 Citations (Scopus)

Abstract

CorrelationClustering is now an established problem in the algorithms and constrained clustering communities. With the requirement that at most two clusters be formed, the minimisation problem is related to the study of signed graphs in the social psychology community, and has applications in statistical mechanics and biological networks. Although a PTAS exists for this problem, its running time is impractical. We therefore introduce a number of new algorithms for 2CC, including two that incorporate some notion of local search. In particular, we show that the algorithm we call PASTA-toss is a 2-approximation on complete graphs. Experiments confirm the strong performance of the local search approaches, even on non-complete graphs, with running time significantly lower than rival approaches.

Original languageEnglish
Title of host publicationAlgorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Pages308-319
Number of pages12
Volume5193 LNCS
DOIs
Publication statusPublished - 2008
Externally publishedYes
EventEuropean Symposium on Algorithms 2008 - Karlsruhe, Germany
Duration: 15 Sep 200817 Sep 2008
Conference number: 16th
http://www.springer.com/la/book/9783540877431

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5193 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Symposium on Algorithms 2008
Abbreviated titleESA 2008
CountryGermany
CityKarlsruhe
Period15/09/0817/09/08
OtherAlgorithms - ESA 2008
16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings
Editors: Mehlhorn, Kurt (Ed.)
Internet address

Cite this

Coleman, T., Saunderson, J., & Wirth, A. (2008). A local-search 2-approximation for 2-correlation-clustering. In Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings (Vol. 5193 LNCS, pp. 308-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS). https://doi.org/10.1007/978-3-540-87744-8-26