BARC talk by Vincent Cohen-Addad

Abstract:

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.