---
title: "The Computational Complexity of Almost Stable Clustering with Penalties"
authors:
  - "Farnam Mansouri"
  - "Sandra Zilles"
  - "Kamyar Khodamoradi"
doi: "10.24963/ijcai.2026/517"
url: "https://ijcai.org/proceedings/2026/517"
pdf: "https://ijcai.org/proceedings/2026/0517.pdf"
venue: "Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence"
year: 2026
pages: "4643-4650"
track: "Main Track"
keywords:
  - "Machine Learning: Clustering"
  - "Machine Learning: Learning theory"
---

# The Computational Complexity of Almost Stable Clustering with Penalties

Farnam Mansouri, Sandra Zilles, Kamyar Khodamoradi

*Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence*, pages 4643-4650. DOI: [10.24963/ijcai.2026/517](https://doi.org/10.24963/ijcai.2026/517)

## Abstract

We investigate the complexity of stable (or perturbation-resilient) instances of k-Means and k-Median clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces, we adopt a more general notion of stability, termed "almost stable", known from the literature as (alpha,epsilon)-perturbation resilience. Additionally, we extend our results to k-Means/k-Median 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 k-Means/k-Median (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and (1 + 1/poly(n))-stable instances of k-Means/k-Median (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).