The Computational Complexity of Almost Stable Clustering with Penalties

Farnam Mansouri; Sandra Zilles; Kamyar Khodamoradi

IJCAI 20260 citations

The Computational Complexity of Almost Stable Clustering with Penalties

Farnam Mansouri, Sandra Zilles, Kamyar Khodamoradi

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).

Machine Learning: ClusteringMachine Learning: Learning theory

BibTeX

@inproceedings{ijcai2026_thecomputational,
  title = {The Computational Complexity of Almost Stable Clustering with Penalties},
  author = {Farnam Mansouri and Sandra Zilles and Kamyar Khodamoradi},
  booktitle = {IJCAI 2026},
  year = {2026}
}