首次证明ℓ₂²最小化聚类问题难以逼近超过1.056倍，且给出高效近似算法。
On Approximability of $\ell_2^2$ Min-Sum Clustering
- 提出首个ℓ₂²聚类问题的近似难度下界，突破原有未知状态。
- 在平衡约翰逊覆盖假设下，硬性逼近因子达1.327，揭示理论极限。
- 设计近乎线性时间参数化近似方案，适合高维小规模聚类场景。
ℓ₂²最小化k-聚类问题要求将输入点集划分为k个簇C₁,…,Cₖ，以最小化∑_{i=1}^k ∑_{p,q∈C_i} ‖p−q‖₂²。尽管该问题是NP-hard，但其近似难度尚不明确。本文首次建立该问题的近似困难性结果：即使在多项式时间内，也难以实现优于1.056的逼近比；若假设平衡版约翰逊覆盖假设成立，则该下界可提升至1.327。随后，我们设计了一个几乎线性时间的参数化全多项式近似方案（PTAS），运行时间为O(n^{1+o(1)} d·exp((k·ε⁻¹)^{O(1)}))，其中d为数据维度。最后，在学习增强设定下，若存在一个提供点标签的预言机，可诱导出近似最优解（允许最多α∈[0,½)的对抗误差），我们给出一个多项式时间算法，输出(1+γα)/(1−α)²-近似解，其中γ>0为常数。
原文摘要 · Abstract (English)
The $\ell_2^2$ min-sum $k$-clustering problem is to partition an input set into clusters $C_1,\ldots,C_k$ to minimize $\sum_{i=1}^k\sum_{p,q\in C_i}\|p-q\|_2^2$. Although $\ell_2^2$ min-sum $k$-clustering is NP-hard, it is not known whether it is NP-hard to approximate $\ell_2^2$ min-sum $k$-clustering beyond a certain factor. In this paper, we give the first hardness-of-approximation result for the $\ell_2^2$ min-sum $k$-clustering problem. We show that it is NP-hard to approximate the objective to a factor better than $1.056$ and moreover, assuming a balanced variant of the Johnson Coverage Hypothesis, it is NP-hard to approximate the objective to a factor better than 1.327. We then complement our hardness result by giving a nearly linear time parameterized PTAS for $\ell_2^2$ min-sum $k$-clustering running in time $O\left(n^{1+o(1)}d\cdot \exp((k\cdot\varepsilon^{-1})^{O(1)})\right)$, where $d$ is the underlying dimension of the input dataset. Finally, we consider a learning-augmented setting, where the algorithm has access to an oracle that outputs a label $i\in[k]$ for input point, thereby implicitly partitioning the input dataset into $k$ clusters that induce an approximately optimal solution, up to some amount of adversarial error $α\in\left[0,\frac{1}{2}\right)$. We give a polynomial-time algorithm that outputs a $\frac{1+γα}{(1-α)^2}$-approximation to $\ell_2^2$ min-sum $k$-clustering, for a fixed constant $γ>0$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。