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 -approximation with amortized update time. Prior to our work Behnezhad et al. in SODA 2023 achieved a -approximation with expected update time in edge streams which translates in vertex streams to an -update time where is the maximum possible degree. Finally we complement our theoretical analysis with experiments on real world data.
Chat is not available.