# On Approximability of ℓ22 Min-Sum Clustering

arXiv: https://arxiv.org/abs/2412.03332 · HTML: https://mlsanity.com/paper/2412.03332/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 80 references that are in the map.
- First posted on arXiv 4 Dec 2024.

## Builds on (most cited first, 30 of 42)

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Solving Empirical Risk Minimization in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1905.04447/) (2019)
- [Faster Fundamental Graph Algorithms via Learned Predictions](https://mlsanity.com/paper/2204.12055/) (2022)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Learning-Augmented k-means Clustering](https://mlsanity.com/paper/2110.14094/) (2021)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Learning Predictions for Algorithms with Predictions](https://mlsanity.com/paper/2202.09312/) (2022)
- [Improved and Simplified Inapproximability for k-means](https://mlsanity.com/paper/1509.00916/) (2015)
- [Online Algorithms with Multiple Predictions](https://mlsanity.com/paper/2205.03921/) (2022)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Triangle and Four Cycle Counting with Predictions in Graph Streams](https://mlsanity.com/paper/2203.09572/) (2022)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis](https://mlsanity.com/paper/2302.06832/) (2023)
- [Online Facility Location with Predictions](https://mlsanity.com/paper/2110.08840/) (2021)
- [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015)
- [On Approximability of Clustering Problems Without Candidate Centers](https://mlsanity.com/paper/2010.00087/) (2020)
- [(Optimal) Online Bipartite Matching with Degree Information](https://mlsanity.com/paper/2110.11439/) (2021)

## Built on by (most cited first, 1 of 1)

- [Transductive and Learning-Augmented Online Regression](https://mlsanity.com/paper/2510.03917/) (2025)

## Abstract (arXiv)

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.