Universitätssiegel Lehrstuhllogo

Universität zu Köln

Department Mathematik/Informatik, Abteilung Informatik

Arbeitsgruppe Jun.- Prof. Dr. Melanie Schmidt

Hauptseminar Clustering mit Nebenbedingungen

Veranstalter
Jun.- Prof. Dr. Melanie Schmidt
Lukas Drexler
Julian Wargalla
Termine
Blockseminar Anfang September
Kontakt
Jun.-Prof. Melanie Schmidt
Julian Wargalla (Bewerbung/Anmeldung)

Inhalte

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.

Themen

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
Liz Heck Privacy Preserving Clustering with Constraints
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