论文标题
关于非均匀$ k $ center的扰动弹性
On Perturbation Resilience of Non-Uniform $k$-Center
论文作者
论文摘要
Chakrabarty，Goyal和Krishnaswamy [iCalp，2016]最近提出了非均匀的$ K $中心（NUKC）问题，作为经典$ K $中心聚类问题的概括。在NUKC中，给定一个$ n $点$ p $在度量空间中和非阴性数字$ r_1，r_2，r_2，\ ldots，r_k $，目标是找到最小的扩张$α$，并选择以$ p $ $ p $的$ p $ $ p $ $ p $ $ 1 \ le i \ le i \ le i \ le i i的$ p $的$ p $，选定的球的结合。他们表明，即使在树准指标中，问题也是在任何因素内都可以近似的NP。另一方面，他们设计了一种“双标准”常数近似算法，该算法使用恒定时间$ k $ balls。令人惊讶的是，即使在$ r_i $属于固定尺寸3的特殊情况下，也没有真正的近似值。我们表明，当$ r_i $属于恒定尺寸的集合时，在2次扰动弹性下的问题是多项式时间。但是，我们表明扰动弹性在一般情况下无济于事。特别是，我们的发现意味着即使有扰动弹性，也无法希望找到任何“良好”近似值。
The Non-Uniform $k$-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical $k$-center clustering problem. In NUkC, given a set of $n$ points $P$ in a metric space and non-negative numbers $r_1, r_2, \ldots , r_k$, the goal is to find the minimum dilation $α$ and to choose $k$ balls centered at the points of $P$ with radius $α\cdot r_i$ for $1\le i\le k$, such that all points of $P$ are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a "bi-criteria" constant approximation algorithm that uses a constant times $k$ balls. Surprisingly, no true approximation is known even in the special case when the $r_i$'s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the $r_i$'s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any "good" approximation for the problem.
