Combinatorial Optimization Reading Group- Adam Brown

Title: Stability Yields a PTAS for k-Median and k-Means Clustering

Abstract: Previously, we have seen a variety of approximation methods for k-median, and last week we saw that assumptions on the structure of our clustering instances can lead to better guarantees. In their work of the same title, Pranjal Awasthi, Avrim Blum, and Or Sheffet introduce the notion of weak deletion stability for k-means and k-median instances and use this assumption to obtain a PTAS.
A k-median instance is weak deletion stable if for every pair of clusters in an optimal clustering when we reassign all points in one to the other this increases the objective cost by a factor of at least (1+\alpha) for some constant \alpha > 0. I will present their algorithm, which obtains a (1 + \epsilon)-approximation for such k-median instances, and discuss how the technique is extended to k-means