TCS Talk - Static to Dynamic Correlation Clustering
Date
Monday, January 19, 2026 11:30 - 12:30
Speaker
David Rasmussen Lolck (University of Copenhagen)
Location
Central Bldg / O1 / Mondi 2a (I01.O1.008)
Series
Seminar/Talk
Host
Monika Henzinger
Contact
Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla (2004). The input is an unweighted, undirected, simple graph. The goal is to cluster (partition) the vertices so as to minimize the number of edges between vertices in different clusters and missing edges between vertices inside the same cluster. This problem has a wide number of applications in data mining and machine learning. We will focus on the dynamic version of this problem, where edges are added or deleted one by one, and the goal is to maintain a clustering during these updates. This talk will present a general framework that transforms existing static correlation clustering algorithms into fully-dynamic ones that work against an adaptive adversary.
In this talk, I will show how to apply the framework to known efficient static correlation clustering algorithms, starting from the classic 3-approximate Pivot algorithm by Ailon, Charikar, and Newman (2008). Applied to the recent near-linear 1.485-approximation algorithm by Cao et al. (2025), we get a 1.485-approximation fully-dynamic algorithm that works with worst-case constant update time. The original static algorithm gets its approximation ratio with constant probability, and we get the same against an adaptive adversary. Previous dynamic algorithms for correlation clustering had approximation ratios around 3 in expectation against oblivious adversaries.