BARC talk by Vincent Cohen-Addad

Recent Progress on Correlation Clustering: The Power of Sherali-Adams and New Practical insights.

Correlation clustering is a classic model for clustering with several applications in data mining and unsupervised machine learning. In this problem, we are given a complete graph where each edge is labeled + or -; and the goal is to find a partition of the vertex set so as to minimize the number of + edges across the parts of the partition plus the number of – edges within the parts of the partition.

We will first present a new result showing that a constant number of rounds of the Sherali-Adams hierarchy yields a strict improvement over the natural LP: We present a Sherali-Adams-based approximation of 1.994-approximation and over the 2.06-approximation of Chawla, Makarychev, Schramm, Yaroslavtsev based on rounding the natural LP (which is known to have an integrality gap of 2).
We will then review several recent ideas which have led to practical constant factor approximations to Correlation Clustering in various setups: distributed and parallel environments, differentially-private algorithms, dynamic algorithms, or sublinear time algorithms.

This is a combination of joint works with Euiwoong Lee, Shi Li, Alantha Newman, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski, Chenglin Fan and Andreas Maggiori.


Vincent Cohen-Addad is a research scientist at Google Research, developing algorithms for machine learning, data mining, and network design applications.

Vincent Cohen-Addad graduated from École Normale Supérieure in Paris, and was a Marie Sklodowska-Curie Fellow at BARC, University of Copenhagen.

He received the EATCS Distinguished Dissertation Award 2016 for his Ph. D. thesis, and won the Best Paper Award at SoCG 2019. He joined CNRS (France) in 2017 and Google Research in 2020. He was an invited plenary speaker at APPROX'22.

As an alumni of BARC 2017 we look forward to welcoming Vincent back to BARC for his visit.