Wir besprechen Approximationsalgorithmen für Clusteringprobleme, beginnend mit den ersten konstanten Approximationsalgorithmen für die Standardformulierungen von Facility Location und k-median. Im Anschluss betrachten wir neuere Arbeiten.
| Name | Paper | |
|---|---|---|
| 11.05.20 | Melanie | 4-Approximation für Facility Location durch LP Runden |
| 18.05.20 | Melanie | 8-Approximation für k-median durch LP Runden |
| 25.05.20 | Lukas | Primal-Dualer Algorithmus für Facility Location |
| 08.06.20 | Lukas | Primal-Dualer Algorithmus für k-median |
| 22.06.20 | Anna A. | Lokale Suche für Facility Location |
| 29.06.20 | Julian | k-means++ |