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

Abstract

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$ min-sum $k$-clustering is NP-hard, it is not known whether it is NP-hard to approximate ${\ell }_2^2$ min-sum $k$-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the ${\ell }_2^2$ min-sum $k$-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than $1.056$ and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a nearly linear time parameterized PTAS for ${\ell }_2^2$ min-sum $k$-clustering running in time $O\left(n^{1+o(1)}d\cdot \exp ((k\cdot {\epsilon }^{-1}{)}^{O(1)})\right)$, where $d$ is the underlying dimension of the input dataset. Finally, we consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label $i\in [k]$ for input point, thereby implicitly partitioning the input dataset into $k$ clusters that induce an approximately optimal solution, up to some amount of adversarial error $\hat{I}\pm \in \left[0,\frac{1}{2}\right)$. We give a polynomial-time algorithm that outputs a $\frac{1+{\hat{I}}^3\hat{I}\pm }{(1-\hat{I}\pm {)}^2}$-approximation to ${\ell }_2^2$ min-sum $k$-clustering, for a fixed constant ${\hat{I}}^3>0$.