In this seminar we will discuss results and open questions from the current research on center based clustering algorithms. We will particularly pay attention to the k-means method, which is one of the most frequently used clustering techniques. As preparation we strongly recommend all participants to read the survey by Awasthi and Balcan [AB13].

Every participant is asked to present the results of one of the following papers. Feel free to contact us, if you already want to start working on some specific topic.

On October 16, 10:15 we will have a preliminary meeting in which the remaining topics will be assigned and all organizational questions will be discussed. Further topics will be added if needed. If you plan to attend the seminar please let us know in advance by email.

Skript/Folien:

• Slides of the Preliminary Meeting

• [AB13] Pranjal Awasthi and Nina Balcan. Center Based Clustering: A Foundational Perspective. Handbook of Cluster Analysis: 1-29 (2014).
• [AV07] David Arthur and Sergej Vassilvitskii. K-Means++: The Advantages of Careful Seeding. SODA 2007: 1027-1035.
• [BBG13] Maria-Florina Balcan and Avrim Blum and Anupam Gupta. Clustering under Approximation Stability. J. ACM 60(2): 8 (2013).
• [HS05] Sariel Har-Peled and Bardia Sadri. How Fast is the K-Means Method?. Algorithmica 41(3): 185-202 (2005).
• [KMNPSW04] Tapas Kanungo and David M. Mount and Nathan S. Netanyahu and Christine D. Piatko and Ruth Silverman and Angela Y. Wu. A Local Search Approximation Algorithm for K-Means Clustering. Comput. Geom. 28(2-3): 89-112 (2004).
• [ORSS12] Rafail Ostrovsky and Yuval Rabani and Leonard J. Schulman and Chaitanya Swamy. The Effectiveness of Lloyd-Type Methods for the K-Means Problem. J. ACM 59(6): 28 (2012).