Pivot based correlation clustering in the presence of good clusters
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915857594056704 |
|---|---|
| author | Lolck, David Rasmussen Thorup, Mikkel Yan, Shuyi |
| author_facet | Lolck, David Rasmussen Thorup, Mikkel Yan, Shuyi |
| contents | The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM'08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some very good clusters, e.g., a complete graph minus a matching. By removing all good clusters before we make each pivot step, we show that this improves the approximation ratio to $2.9991$. To aid in this, we also show how our proposed algorithm performs on synthetic datasets, where the algorithm performs remarkably well, and shows improvements over both the algorithm for locating good clusters and the classic pivot algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_12052 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Pivot based correlation clustering in the presence of good clusters Lolck, David Rasmussen Thorup, Mikkel Yan, Shuyi Data Structures and Algorithms The classic pivot based clustering algorithm of Ailon, Charikar and Chawla [JACM'08] is factor 3, but all concrete examples showing that it is no better than 3 are based on some very good clusters, e.g., a complete graph minus a matching. By removing all good clusters before we make each pivot step, we show that this improves the approximation ratio to $2.9991$. To aid in this, we also show how our proposed algorithm performs on synthetic datasets, where the algorithm performs remarkably well, and shows improvements over both the algorithm for locating good clusters and the classic pivot algorithm. |
| title | Pivot based correlation clustering in the presence of good clusters |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.12052 |