# Partial k-means to avoid outliers, mathematical programming formulations, complexity results

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2023.

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

- [Modified K-means Algorithm with Local Optimality Guarantees](https://mlsanity.com/paper/2506.06990/) (2025)

## Abstract (arXiv)

A well-known bottleneck of Min-Sum-of-Square Clustering (MSSC, the celebrated k-means problem) is to tackle the presence of outliers. In this paper, we propose a Partial clustering variant termed PMSSC which considers a fixed number of outliers to remove. We solve PMSSC by Integer Programming formulations and complexity results extending the ones from MSSC are studied. PMSSC is NP-hard in Euclidean space when the dimension or the number of clusters is greater than 2. Finally, one-dimensional cases are studied: Unweighted PMSSC is polynomial in that case and solved with a dynamic programming algorithm, extending the optimality property of MSSC with interval clustering. This result holds also for unweighted k-medoids with outliers. A weaker optimality property holds for weighted PMSSC, but NP-hardness or not remains an open question in dimension one.