Algorithmic advances on metric and graph clustering (Part 2) Vincent Cohen-Addad

Vincent Cohen-Addad (Google, Zurich)

Details:
Abstract: Clustering algorithms are at the core of unsupervised machine learning and data analysis techniques. Given a set of data elements, the goal of a clustering is to partition a dataset in such a way that data elements in the same part are more similar to each other than data elements in different parts. Clustering problems arise in large variety of applications ranging from bioinformatics to computer vision and as such are very basic problems.
In these two talks, we will present both metric clustering (Part 1) and graph clustering (Part 2) problems. We will first illustrate some recent advances in the complexity of the classic k-median and k-means problems, two popular objective functions for metric clustering, via some recent developments on the fixed-parameter tractability of the objectives and hardness of approximation. We will then describe new approximation algorithms for metric hierarchical clustering.
In the second part of the talks, we will present a new perspective on the classic correlation clustering objective that leads to new efficient distributed algorithms for the problem, together with a beyond-the-worst-case analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.