Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.