1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911067167260672 |
|---|---|
| author | Lee, Dahoon Fan, Chenglin Lee, Euiwoong |
| author_facet | Lee, Dahoon Fan, Chenglin Lee, Euiwoong |
| contents | Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on the clusters. Unlike traditional Correlation Clustering, which only deals with binary $(+/-)$ relationships, CCC captures richer relational structures. Despite its importance, improving the approximation for CCC has been difficult due to the limitations of standard LP relaxations. We present a randomized $1.64$-approximation algorithm to the CCC problem, significantly improving the previous factor of $2.15$. Our approach extends the cluster LP framework to the chromatic setting by introducing a chromatic cluster LP relaxation and an rounding algorithm that utilizes both a cluster-based and a greedy pivot-based strategy. The analysis bypasses the integrality gap of $2$ for the CCC version of standard LP and highlights the potential of the cluster LP framework to address other variants of clustering problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15417 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP Lee, Dahoon Fan, Chenglin Lee, Euiwoong Data Structures and Algorithms Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on the clusters. Unlike traditional Correlation Clustering, which only deals with binary $(+/-)$ relationships, CCC captures richer relational structures. Despite its importance, improving the approximation for CCC has been difficult due to the limitations of standard LP relaxations. We present a randomized $1.64$-approximation algorithm to the CCC problem, significantly improving the previous factor of $2.15$. Our approach extends the cluster LP framework to the chromatic setting by introducing a chromatic cluster LP relaxation and an rounding algorithm that utilizes both a cluster-based and a greedy pivot-based strategy. The analysis bypasses the integrality gap of $2$ for the CCC version of standard LP and highlights the potential of the cluster LP framework to address other variants of clustering problems. |
| title | 1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.15417 |