Seminar on Algorithms: Clustering


Clustering is a fundamental task in data science that often arises in real-world applications. In the past decades several alternative formulations of the clustering problem have been proposed. These have led to a variety of algorithms, both exact and approximate, using a broad range of optimization techniques such as local search, core-sets, linear programming, etc. Studying the inherent hardness of clustering has led to deep theoretical results, combining insights from geometry and graph theory.

In this seminar/reading group we will study representative and recent results related to clustering, with a focus on algorithmic and complexity aspects. We present/discuss one or two papers each week.

Requirements: ALP3/HA or similar algorithmic background, mathematical maturity.

welcome announcement


introduction and topics slides


feedback form for presentations


Presentation calendar:

Date Topic Presenter
5th Nov k-center greedy approximation and hardness Clea Peter
12th Nov


Wenli Xu
  NP-hardness of k-means Florian Alex
19th Nov hierarchical clustering Yao Zheng
  impossibility of clustering Niclas Schwarzlose
26th Nov sampling approximation for k-means

Clemens Mosig

  LP-relaxation for median clustering Hannah Troppens
3rd Dec graph clustering: cut-based methods Lilli Joppien
  spectral method for expander-decomposition Theresa Allner
10th Dec

correlation clustering

Tim Haarseim
  explainable k-means clustering Raimi Solorzano
17th Dec clustering stability Vitalij Krotov
  capacitated clustering Sandra Lukanek
7th Jan

smoothed analysis of k-means

streaming clustering

Timo Oehme

Claas Fandré

14th Jan spectral clustering Boyan Hristov
28th Jan

local search for clustering I

local search for clustering II

Numan Fidan

Fang Lin