Seminars

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

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

<br>
In the second part of the talks, we will present a new perspective on the classic correlation clustering
<br>
objective that leads to new efficient distributed algorithms for the problem, together with a beyond-the-worst-case
<br>
analysis of the Louvain algorithm for finding the maximum modularity graphs clustering.
<br>

Microsoft Teams Link:
<br>
<a href="Link
</a>
<br>

<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Arindam Khan