On Approximability of ℓ22 Min-Sum Clustering

The ℓ22 min-sum k-clustering problem is to partition an input set into clusters C1,ldots,Ck to minimize sumi=1ksump,q∈ Ci|p-q|22. Although ℓ22 min-sum k-clustering is NP-hard, it is not known whether it is NP-hard to approximate ℓ22 min-sum k-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the ℓ22 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 ℓ22 min-sum k-clustering running in time Oleft(n1+o(1)d· exp((k·varepsilon-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∈[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 α∈left[0,frac12right). We give a polynomial-time algorithm that outputs a frac1+γα(1-α)2-approximation to ℓ22 min-sum k-clustering, for a fixed constant γ>0.