研究带惩罚的聚类问题在近似稳定条件下的计算复杂性。
The Computational Complexity of Almost Stable Clustering with Penalties
- 提出近似稳定概念，推广传统稳定性定义
- 发现部分情形可在多项式时间内求解
- 证明多数情况需超多项式时间，适合理论研究者
我们研究度量空间中双倍维数较小的k-MEANS和k-MEDIAN聚类问题在近似稳定条件下的计算复杂性。虽然这些问题是低维欧氏空间中乘法扰动鲁棒性下广泛研究的课题，但本文采用更一般的稳定概念——近似稳定，其更接近Balcan和Liang（2016）提出的(α, ε)-扰动鲁棒性。此外，将结果扩展至带惩罚的k-MEANS/k-MEDIAN问题，其中每个数据点可被分配至聚类中心或支付惩罚。我们证明某些近似稳定情形下的带惩罚问题可在多项式时间内求解。为补充此结果，还分析了近似稳定实例及(1 + 1/poly(n))-稳定实例的难解性，基于广泛接受的指数时间假设（ETH），证明任何精确算法均需超多项式时间。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。