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

Tom Coleman; James Saunderson; Anthony Wirth

doi:10.1007/978-3-540-87744-8-26

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

Tom Coleman, James Saunderson, Anthony Wirth

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

31 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 language	English
Title of host publication	Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings
Pages	308-319
Number of pages	12
Volume	5193 LNCS
DOIs	https://doi.org/10.1007/978-3-540-87744-8-26
Publication status	Published - 2008
Externally published	Yes
Event	European Symposium on Algorithms 2008 - Karlsruhe, Germany Duration: 15 Sept 2008 → 17 Sept 2008 Conference number: 16th http://www.springer.com/la/book/9783540877431

Publication series

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

Conference

Conference	European Symposium on Algorithms 2008
Abbreviated title	ESA 2008
Country/Territory	Germany
City	Karlsruhe
Period	15/09/08 → 17/09/08
Other	Algorithms - ESA 2008 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008, Proceedings Editors: Mehlhorn, Kurt (Ed.)
Internet address	http://www.springer.com/la/book/9783540877431

Access to Document

10.1007/978-3-540-87744-8-26

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

@inproceedings{e498ef9dfb674dcfa9fb616c5aa74fc9,

title = "A local-search 2-approximation for 2-correlation-clustering",

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.",

author = "Tom Coleman and James Saunderson and Anthony Wirth",

year = "2008",

doi = "10.1007/978-3-540-87744-8-26",

language = "English",

isbn = "3540877436",

volume = "5193 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "308--319",

booktitle = "Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings",

note = "European Symposium on Algorithms 2008, ESA 2008 ; Conference date: 15-09-2008 Through 17-09-2008",

url = "http://www.springer.com/la/book/9783540877431",

}

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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5193 LNCS, pp. 308-319, European Symposium on Algorithms 2008, Karlsruhe, Baden-Württemberg, Germany, 15/09/08. https://doi.org/10.1007/978-3-540-87744-8-26

A local-search 2-approximation for 2-correlation-clustering. / Coleman, Tom; Saunderson, James; Wirth, Anthony.
Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings. Vol. 5193 LNCS 2008. p. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5193 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Coleman, Tom

AU - Saunderson, James

AU - Wirth, Anthony

N1 - Conference code: 16th

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/57749169020

U2 - 10.1007/978-3-540-87744-8-26

DO - 10.1007/978-3-540-87744-8-26

M3 - Conference Paper

AN - SCOPUS:57749169020

SN - 3540877436

SN - 9783540877431

VL - 5193 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 308

EP - 319

BT - Algorithms - ESA 2008 - 16th Annual European Symposium, Proceedings

T2 - European Symposium on Algorithms 2008

Y2 - 15 September 2008 through 17 September 2008

ER -

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

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this