MA-INF 1319 - Cluster Analysis


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!

General Information

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


When Where Start Lecturer
Wednesday, 12:30-14:00 INF / Room 2.050 October 17th Rösner
Friday, 14:00-15:30 INF / Room 2.050 October 19th Rösner

Problem Sets

  • 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)


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.

Page Tools