Skip to yearly menu bar Skip to main content


Spotlight Poster

Dynamic Correlation Clustering in Sublinear Update Time

Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis

Hall C 4-9 #1016

Abstract: We study the classic problem of correlation clustering in dynamic vertex streams. In this setting, vertices are either added or randomly deleted over time, and each vertex 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(polylogn) amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a 5-approximation with O(1) expected update time in edge streams which translates in vertex 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.

Chat is not available.