The Computational Complexity of Almost Stable Clustering with Penalties

Mansouri, Farnam; Zilles, Sandra; Khodamoradi, Kamyar

doi:10.24963/ijcai.2026/517

The Computational Complexity of Almost Stable Clustering with Penalties

Farnam Mansouri, Sandra Zilles, Kamyar Khodamoradi

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 4643-4650.

https://doi.org/10.24963/ijcai.2026/517

Keywords

Machine Learning: Clustering
Machine Learning: Learning theory

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

Farnam Mansouri, Sandra Zilles, and Kamyar Khodamoradi. 2026. The Computational Complexity of Almost Stable Clustering with Penalties. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 4643–4650. https://doi.org/10.24963/ijcai.2026/517

@inproceedings{ijcai2026p517,
  title     = {The Computational Complexity of Almost Stable Clustering with Penalties},
  author    = {Mansouri, Farnam and Zilles, Sandra and Khodamoradi, Kamyar},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {4643--4650},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/517},
  url       = {https://doi.org/10.24963/ijcai.2026/517},
}

TY  - CPAPER
TI  - The Computational Complexity of Almost Stable Clustering with Penalties
AU  - Mansouri, Farnam
AU  - Zilles, Sandra
AU  - Khodamoradi, Kamyar
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 4643
EP  - 4650
DO  - 10.24963/ijcai.2026/517
UR  - https://doi.org/10.24963/ijcai.2026/517
ER  -