View all Seminars  |  Download ICal for this event

Algorithmic advances on metric and graph clustering (Part 1)

Series: Theory Seminar

Speaker: Dr. Vincent Viallat Cohen-Addad Research Scientist Google Zürich

Date/Time: Oct 08 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

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.
Microsoft Teams Link:

For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Arindam Khan