# Min-Sum Clustering (with Outliers)

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2020.

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

- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [On Approximability of ℓ22 Min-Sum Clustering](https://mlsanity.com/paper/2412.03332/) (2024)

## Abstract (arXiv)

We give a constant factor polynomial time pseudo-approximation algorithm for min-sum clustering with or without outliers. The algorithm is allowed to exclude an arbitrarily small constant fraction of the points. For instance, we show how to compute a solution that clusters 98% of the input data points and pays no more than a constant factor times the optimal solution that clusters 99% of the input data points. More generally, we give the following bicriteria approximation: For any eps > 0, for any instance with n input points and for any positive integer n'≤ n, we compute in polynomial time a clustering of at least (1-eps) n' points of cost at most a constant factor greater than the optimal cost of clustering n' points. The approximation guarantee grows with frac1eps. Our results apply to instances of points in real space endowed with squared Euclidean distance, as well as to points in a metric space, where the number of clusters, and also the dimension if relevant, is arbitrary (part of the input, not an absolute constant).