**Lecture Notes**: The lecture notes have last been updated on the 30th of October and now cover lectures 1-4.

**Oral Exams**: The exams are oral exams. The dates will be announced later. The first exam date will lie somewhere between the 4th and 8th of February, 2019.

**Room**: We are in room 2.078 from now on!

**Note**: If you attend the lecture and have not done so yet, please send me a short email to this email address. Thank you!

The content of this lecture is the theoretical analysis of approximation algorithms for cluster analysis, in particular covering the following areas:

- Approximation algorithms for k-center, k-median and k-means
- Different techniques for approximation algorithms, including ILP-based techniques and local search
- Clustering of Big Data and in Data Streams
- Analysis of common clustering heuristics
- Practically efficient methods with theoretical guarantees

When | Where | Start | Lecturer |
---|---|---|---|

Tuesday, 10:15-11:45 | INF / Room 2.078 | October 09th | Schmidt |

- Problem Set 1 (hand in until October 16th, to be discussed October 17th and October 19th)
- Problem Set 2 (hand in until October 23th, to be discussed October 24th and October 26th)
- Problem Set 3 (hand in until October 30th, to be discussed October 31st and November 2nd)
- Problem Set 4 (hand in until November 6th, to be discussed November 7th and November 9th)
- November 14th and November 16th tutorials will be for repetition and questions and without a new exercise sheet
- Problem Set 5 (hand in until November 20th, to be discussed November 21st and November 23rd)

Date | |
---|---|

October 09 | 1 Introduction 2 The happy world of k-center 2.1 Definition 2.2 A simple and elegant 2-approximation |

October 16 | 2.3 A matching lower bound 2.4 Incremental and hierarchical clustering |

October 23 | 2.4 continued: Proof 2.5 Another elegant 2-approximation |

October 30 | 2.6 A streaming algorithm for k-center |

November 6 | –cancelled due to illness– |

November 13 | 2.7 The k-center problem with outliers 2.8 Fair k-center |

The Lecture notes cover the content of the lecture and are updated after each lecture.