Understanding the Cluster LP for Correlation Clustering
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917051374764032 |
|---|---|
| author | Cao, Nairen Cohen-Addad, Vincent Lee, Euiwoong Li, Shi Newman, Alantha Vogl, Lukas |
| author_facet | Cao, Nairen Cohen-Addad, Vincent Lee, Euiwoong Li, Shi Newman, Alantha Vogl, Lukas |
| contents | In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either $+$ or $-$, and the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev (STOC 2015) gave a 2.06-approximation by providing a near-optimal rounding of the standard LP, and Cohen-Addad, Lee, Li, and Newman (FOCS 2022, 2023) finally bypassed the integrality gap of 2 for this LP giving a $1.73$-approximation for the problem.
In order to create a simple and unified framework for Correlation Clustering similar to those for typical approximate optimization tasks, we propose the cluster LP as a strong linear program for Correlation Clustering. We demonstrate the power of the cluster LP by presenting new rounding algorithms, and providing two analyses, one analytically proving a 1.56-approximation and the other solving a factor-revealing SDP to show a 1.485-approximation. Both proofs introduce principled methods by which to analyze the performance of the algorithm, resulting in a significantly improved approximation guarantee.
Finally, we prove an integrality gap of $4/3$ for the cluster LP, showing our 1.485-upper bound cannot be drastically improved. Our gap instance directly inspires an improved NP-hardness of approximation with a ratio $24/23 \approx 1.042$; no explicit hardness ratio was known before. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17509 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Understanding the Cluster LP for Correlation Clustering Cao, Nairen Cohen-Addad, Vincent Lee, Euiwoong Li, Shi Newman, Alantha Vogl, Lukas Data Structures and Algorithms In the classic Correlation Clustering problem introduced by Bansal, Blum, and Chawla (FOCS 2002), the input is a complete graph where edges are labeled either $+$ or $-$, and the goal is to find a partition of the vertices that minimizes the sum of the +edges across parts plus the sum of the -edges within parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev (STOC 2015) gave a 2.06-approximation by providing a near-optimal rounding of the standard LP, and Cohen-Addad, Lee, Li, and Newman (FOCS 2022, 2023) finally bypassed the integrality gap of 2 for this LP giving a $1.73$-approximation for the problem. In order to create a simple and unified framework for Correlation Clustering similar to those for typical approximate optimization tasks, we propose the cluster LP as a strong linear program for Correlation Clustering. We demonstrate the power of the cluster LP by presenting new rounding algorithms, and providing two analyses, one analytically proving a 1.56-approximation and the other solving a factor-revealing SDP to show a 1.485-approximation. Both proofs introduce principled methods by which to analyze the performance of the algorithm, resulting in a significantly improved approximation guarantee. Finally, we prove an integrality gap of $4/3$ for the cluster LP, showing our 1.485-upper bound cannot be drastically improved. Our gap instance directly inspires an improved NP-hardness of approximation with a ratio $24/23 \approx 1.042$; no explicit hardness ratio was known before. |
| title | Understanding the Cluster LP for Correlation Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17509 |