Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909133024788480 |
|---|---|
| author | Davies, Sami Moseley, Benjamin Newman, Heather |
| author_facet | Davies, Sami Moseley, Benjamin Newman, Heather |
| contents | This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously $O(1)$-approximate for all $\ell_p$-norms of the disagreement vector; in other words, a combinatorial $O(1)$-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector. In addition, our algorithm is the first combinatorial approximation algorithm for the $\ell_2$-norm objective, and more generally the first combinatorial algorithm for the $\ell_p$-norm objective when $1 < p < \infty$. It is also faster than all previous algorithms that minimize the $\ell_p$-norm of the disagreement vector, with run-time $O(n^ω)$, where $O(n^ω)$ is the time for matrix multiplication on $n \times n$ matrices. When the maximum positive degree in the graph is at most $Δ$, this can be improved to a run-time of $O(nΔ^2 \log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_01534 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering Davies, Sami Moseley, Benjamin Newman, Heather Data Structures and Algorithms Discrete Mathematics This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously $O(1)$-approximate for all $\ell_p$-norms of the disagreement vector; in other words, a combinatorial $O(1)$-approximation of the all-norms objective for correlation clustering. This is the first proof that minimal sacrifice is needed in order to optimize different norms of the disagreement vector. In addition, our algorithm is the first combinatorial approximation algorithm for the $\ell_2$-norm objective, and more generally the first combinatorial algorithm for the $\ell_p$-norm objective when $1 < p < \infty$. It is also faster than all previous algorithms that minimize the $\ell_p$-norm of the disagreement vector, with run-time $O(n^ω)$, where $O(n^ω)$ is the time for matrix multiplication on $n \times n$ matrices. When the maximum positive degree in the graph is at most $Δ$, this can be improved to a run-time of $O(nΔ^2 \log n)$. |
| title | Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2308.01534 |