Stability Yields a PTAS for k-Median and k-Means Clustering.

Pranjal Awasthi, Avrim Blum, Or Sheffet

Browse the full FOCS paper archive.