静5青年讲座 | Combinatorial Algorithms for Correlation Clustering

Correlation clustering is a well-studied problem, first proposed by Bansal, Blum, and Chawla [BBC04]. The input is an unweighted undirected graph and the goal is the best approximation with disjoint cliques. This problem has a wide application in data mining and machine learning. The minimization version is APX-hard. Before 2024, all approximation algorithms with ratio less than 3 are LP-rounding based, which seem to be far away from near linear time implementation. In this talk I will cover some recent breakthroughs on the combinatorial side of correlation clustering, which can both achieve the same approximation ratio 1.485 as the best known LP-based one, and be implemented in near linear time and in sublinear time for dense graph. This approach can also be turned into a efficient dynamic algorithm with edge update against adaptive adversary. This talk is mostly based on the three papers "Combinatorial Correlation Clustering", "Solving the Correlation Cluster LP in Sublinear Time" and "Static to Dynamic Correlation Clustering".

Hanwen Zhang is a forth year PhD student at Copenhagen University, advised by Mikkel Abrahamsen and Mikkel Thorup. He finished his bachelor at Tsinghua University (Yao class) in 2022. His research interest is on the design and analysis of combinatorial optimization algorithms, including geometric packing and covering problems, clustering problem, as well as turning classic combinatorial optimization algorithms to be friendly to user privacy.