Clustering mit Nebenbedingungen
Das Seminar richtet sich ausschließlich an Studierende im Master. Es ist im Bereich der theoretischen Analyse von Clusteringalgorithmen angesiedelt und beschäftigt sich mit Approximationsalgorithmen. Es gibt in der Literatur verschiedene mathematische Zielfunktionen für Clusteringprobleme. Ein Beispiel ist das k-median Problem, beidem Punkte zusammen mit einer Metrik gegeben sind und k Zentren so gewählt werden sollen, dass die Summe der Abstaände aller Punkte zum nächstgelegenen Cluster minimiert wird. Für dieses und auch andere Zielfunktionen wurden im Laufe der Jahrzehnte viele sehr komplexe Approximationsalgorithmen entworfen, die immer bessere Approximationsgarantien erzielen. Sehr viel weniger gut untersucht waren jedoch bisher Clusteringprobleme, bei denen die Wahl der Zentren bzw. die Zuordnung von Punkten zu Zentren durch Nebenbedingungen eingeschränkt wird. Wir wollen in diesem Seminar einige aktuellere Originalarbeiten aufarbeiten, die sich mit Approximationsalgorithmen für Clustering mit Nebenbedingungen beschäftigen. Alle Teilnehmer/innen halten einen auf 45 Minuten angesetzten Vortrag mit anschließender Diskussion. Aktive Teilnahme an der Diskussion und somit auch den Vorträgen wird erwartet. Nach dem Vortrag ist die Bereitstellung von elektronischen Vortragsfolien bzw. eine schriftliche Ausarbeitung (in LaTeX) erforderlich.
| Name | Paper |
|---|---|
| Tobias Hübenthal | The Capacitated k-Center Problem |
| Sebastian Zaun | The Centrality of Trees for Capacitated k-Center |
| Lutz Görgen | LP Rounding for k-Centers with Non-uniform Hard Capacities |
| Lucas Gemein | Achieving Anonymity via Clustering |
| Luka Lukatela | Lower-Bounded Facility Location |
| Alexander Tiebing | Fair Clustering Through Fairlets, On the cost of essentially fair clusterings |
| Lisa Thoma | The Non-Uniform k-Center Problem |
| Diana Sklema | Streaming algorithms for k-center clustering with outliers and with anonymity |
| Vincent Feldmar | Performance guarantees for hierarchical clustering |
| Benjamin Bolm | A cost function for similarity-based hierarchical clustering |
| Jana Pier | Improved Analysis of Complete-Linkage Clustering |