# The Computational Complexity of Almost Stable Clustering with Penalties

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 18 references that are in the map.
- First posted on arXiv 3 Oct 2025.

## Builds on (most cited first, 5 of 5)

- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [On the Local Structure of Stable Clustering Instances](https://mlsanity.com/paper/1701.08423/) (2017)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [The Bane of Low-Dimensionality Clustering](https://mlsanity.com/paper/1711.01171/) (2017)
- [Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means](https://mlsanity.com/paper/1807.05443/) (2018)

## Abstract (arXiv)

We investigate the complexity of stable (or perturbation-resilient) instances of mathrmk-MsmallEANS and mathrmk-MsmallEDIAN clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces (e.g., (Friggstad et al., 2019; Cohen-Addad and Schwiegelshohn, 2017)), we adopt a more general notion of stability, termed ``almost stable'', which is closer to the notion of (α, varepsilon)-perturbation resilience introduced by Balcan and Liang (2016). Additionally, we extend our results to mathrmk-MsmallEANS/mathrmk-MsmallEDIAN with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable mathrmk-MsmallEANS/mathrmk-MsmallEDIAN (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and (1 + frac1poly(n))-stable instances of mathrmk-MsmallEANS/mathrmk-MsmallEDIAN (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).