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.
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 | Tim Haarseim | |
| explainable k-means clustering | Raimi Solorzano | |
| 17th Dec | clustering stability | Vitalij Krotov |
| capacitated clustering | Sandra Lukanek | |
| 7th Jan |
Timo Oehme Claas Fandré |
|
| 14th Jan | spectral clustering | Boyan Hristov |
| 28th Jan |
Numan Fidan Fang Lin |