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.
|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||
|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|
|14th Jan||spectral clustering||Boyan Hristov|