Dynamic Correlation Clustering in Sublinear Update Time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911916035670016 |
|---|---|
| author | Cohen-Addad, Vincent Lattanzi, Silvio Maggiori, Andreas Parotsidis, Nikos |
| author_facet | Cohen-Addad, Vincent Lattanzi, Silvio Maggiori, Andreas Parotsidis, Nikos |
| contents | We study the classic problem of correlation clustering in dynamic node streams. In this setting, nodes are either added or randomly deleted over time, and each node pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an $O(1)$-approximation with $O$(polylog $n$) amortized update time. Prior to our work, Behnezhad, Charikar, Ma, and L. Tan achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in node streams to an $O(D)$-update time where $D$ is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_09137 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic Correlation Clustering in Sublinear Update Time Cohen-Addad, Vincent Lattanzi, Silvio Maggiori, Andreas Parotsidis, Nikos Data Structures and Algorithms Machine Learning We study the classic problem of correlation clustering in dynamic node streams. In this setting, nodes are either added or randomly deleted over time, and each node pair is connected by a positive or negative edge. The objective is to continuously find a partition which minimizes the sum of positive edges crossing clusters and negative edges within clusters. We present an algorithm that maintains an $O(1)$-approximation with $O$(polylog $n$) amortized update time. Prior to our work, Behnezhad, Charikar, Ma, and L. Tan achieved a $5$-approximation with $O(1)$ expected update time in edge streams which translates in node streams to an $O(D)$-update time where $D$ is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data. |
| title | Dynamic Correlation Clustering in Sublinear Update Time |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2406.09137 |