Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912311472553984 |
|---|---|
| author | Assadi, Sepehr Khanna, Sanjeev Putterman, Aaron |
| author_facet | Assadi, Sepehr Khanna, Sanjeev Putterman, Aaron |
| contents | Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of better and better classical algorithms for approximating this problem. Meanwhile, another line of research has focused on porting the classical advances to various sublinear algorithm models, including semi-streaming, Massively Parallel Computation (MPC), and distributed computing. Yet, these latter works typically rely on ad-hoc approaches that do not necessarily keep up with advances in approximation ratios achieved by classical algorithms.
Hence, the motivating question for our work is this: can the gains made by classical algorithms for correlation clustering be ported over to sublinear algorithms in a \emph{black-box manner}? We answer this question in the affirmative by introducing the paradigm of graph de-sparsification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04258 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms Assadi, Sepehr Khanna, Sanjeev Putterman, Aaron Data Structures and Algorithms Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of better and better classical algorithms for approximating this problem. Meanwhile, another line of research has focused on porting the classical advances to various sublinear algorithm models, including semi-streaming, Massively Parallel Computation (MPC), and distributed computing. Yet, these latter works typically rely on ad-hoc approaches that do not necessarily keep up with advances in approximation ratios achieved by classical algorithms. Hence, the motivating question for our work is this: can the gains made by classical algorithms for correlation clustering be ported over to sublinear algorithms in a \emph{black-box manner}? We answer this question in the affirmative by introducing the paradigm of graph de-sparsification. |
| title | Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.04258 |