Chromatic correlation clustering via cluster LP
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917015964352512 |
|---|---|
| author | Abbasi, Fateme An, Hyung-Chan Byrka, Jarosław Lee, Changyeol Shin, Yongho |
| author_facet | Abbasi, Fateme An, Hyung-Chan Byrka, Jarosław Lee, Changyeol Shin, Yongho |
| contents | Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a $(2+\varepsilon)$-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13446 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Chromatic correlation clustering via cluster LP Abbasi, Fateme An, Hyung-Chan Byrka, Jarosław Lee, Changyeol Shin, Yongho Data Structures and Algorithms Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a $(2+\varepsilon)$-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP. |
| title | Chromatic correlation clustering via cluster LP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.13446 |