SPARSE-PIVOT: Dynamic correlation clustering for node insertions
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_ | 1866913923085631488 |
|---|---|
| author | Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan |
| author_facet | Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan |
| contents | We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $O_ε(\log^{O(1)}(n))$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al.~in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01830 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | SPARSE-PIVOT: Dynamic correlation clustering for node insertions Dalirrooyfard, Mina Makarychev, Konstantin Mitrović, Slobodan Data Structures and Algorithms We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of $O_ε(\log^{O(1)}(n))$. Its approximation factor is $20+\varepsilon$, which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al.~in practice. |
| title | SPARSE-PIVOT: Dynamic correlation clustering for node insertions |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.01830 |