The Computational Complexity of Almost Stable Clustering with Penalties

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