{"ID":2861032,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.03143","arxiv_id":"2510.03143","title":"The Computational Complexity of Almost Stable Clustering with Penalties","abstract":"We investigate the complexity of stable (or perturbation-resilient) instances of $\\mathrm{k-M\\small{EANS}}$ and $\\mathrm{k-M\\small{EDIAN}}$ 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 $\\mathrm{k-M\\small{EANS}}$/$\\mathrm{k-M\\small{EDIAN}}$ 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 $\\mathrm{k-M\\small{EANS}}$/$\\mathrm{k-M\\small{EDIAN}}$ (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and $(1 + \\frac{1}{poly(n)})$-stable instances of $\\mathrm{k-M\\small{EANS}}$/$\\mathrm{k-M\\small{EDIAN}}$ (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).","short_abstract":"We investigate the complexity of stable (or perturbation-resilient) instances of $\\mathrm{k-M\\small{EANS}}$ and $\\mathrm{k-M\\small{EDIAN}}$ clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euc...","url_abs":"https://arxiv.org/abs/2510.03143","url_pdf":"https://arxiv.org/pdf/2510.03143v1","authors":"[\"Kamyar Khodamoradi\",\"Farnam Mansouri\",\"Sandra Zilles\"]","published":"2025-10-03T16:15:12Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\",\"cs.LG\"]","methods":"[]","has_code":false}