The Computational Complexity of Almost Stable Clustering with Penalties

Kamyar Khodamoradi, Farnam Mansouri, Sandra Zilles

We investigate the complexity of stable (or perturbation-resilient) instances of $\mathrm{k}-\mathrm{M}\mathrm{EANS}$ and $\mathrm{k}-\mathrm{M}\mathrm{EDIAN}$ clustering problems in metrics with smal…