On Approximability of ${\ell }_2^2$ Min-Sum Clustering

Karthik C. S., Euiwoong Lee, Yuval Rabani +2

The ${\ell }_2^2$ min-sum $k$-clustering problem is to partition an input set into clusters $C_1,\dots ,C_k$ to minimize ${\sum }_{i=1}^k{\sum }_{p,q\in C_i}\Vert p-q{\Vert }_2^2$. Although $\ell_2^2…