Dynamic Correlation Clustering in Sublinear Update Time
<|reference_start|>Dynamic Correlation Clustering in Sublinear Update Time: 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.<|reference_end|>
@article{cohen-addad2024dynamic,
    title={Dynamic Correlation Clustering in Sublinear Update Time},
    author={Vincent Cohen-Addad and Silvio Lattanzi and Andreas Maggiori and Nikos
  Parotsidis},
    journal={arXiv preprint arXiv:2406.09137},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.09137},
    primaryClass={cs.DS cs.LG}
}