k-center Clustering under Perturbation Resilience
k-center Clustering under Perturbation Resilience
复制标题
扰动弹性下的 k 中心聚类
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Colin White
中科院分区：
文献类型：
--
作者：
Maria;Nika Haghtalab;Colin White
k-中心问题是一个经典的和长期研究的设施定位和集群问题，有许多应用在其对称和非对称形式。两个版本的问题在最坏情况下都有严格的近似因子：对称k-中心的2-近似和非对称版本的O（log*（k））-近似。因此，为了改善这些比率，必须超越最坏的情况。在这项工作中，我们采用这种方法，并在称为α-扰动弹性的自然输入稳定性（承诺）条件下为非对称和对称k-中心问题提供了强阳性结果[15]，该条件表明最优解在输入距离的任何α-因子扰动下都不会改变。我们提供的算法，同时提供强有力的保证稳定和不稳定的情况下：我们的算法总是继承聚类近似算法的最坏情况下的保证，并输出最佳的解决方案，如果输入是2-扰动弹性。特别是，我们表明，如果输入只有扰动弹性的一部分数据，我们的算法将返回最佳的集群从该区域的数据是扰动弹性，同时实现最好的最坏情况下的近似保证的其余部分的数据。此外，我们证明了我们的结果是紧的，表明对称k-中心下（2-ε）-扰动弹性是困难的，除非NP = RP。我们的成果的影响是多方面的。首先，据我们所知，非对称k-中心是第一个在最坏情况下难以近似为任何常数因子的问题，但可以在α为常数的扰动弹性下在多项式时间内最优求解。这也是扰动弹性下任何问题的第一个严格结果，即，这是第一次发现α的精确值，使得问题从NP难转变为有效可计算。此外，我们的结果说明了在扰动弹性下对称和非对称k中心实例之间令人惊讶的关系。与近似比不同，对称k-中心很容易求解为2的因子，但不对称k-中心不能近似为任何常数因子，对称和不对称k-中心都可以在对2-扰动的弹性下最佳地求解。最后，我们在只有部分数据满足扰动弹性的设置中的保证使这些算法更适用于现实生活中的实例。
The k-center problem is a canonical and long-studied facility location and clustering problem with many applications in both its symmetric and asymmetric forms. Both versions of the problem have tight approximation factors on worst case instances: a 2-approximation for symmetric k-center and an O(log*(k))-approximation for the asymmetric version. Therefore, to improve on these ratios, one must go beyond the worst case. In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric k-center problems under a natural input stability (promise) condition called α-perturbation resilience [15], which states that the optimal solution does not change under any α-factor perturbation to the input distances. We provide algorithms that give strong guarantees simultaneously for stable and non-stable instances: Our algorithms always inherit the worst-case guarantees of clustering approximation algorithms and output the optimal solution if the input is 2-perturbation resilient. In particular, we show that if the input is only perturbation resilient on part of the data, our algorithm will return the optimal clusters from the region of the data that is perturbation resilient while achieving the best worst-case approximation guarantee on the remainder of the data. Furthermore, we prove that our result is tight by showing symmetric k-center under (2 − ε)-perturbation resilience is hard unless NP = RP. The impact of our results is multifaceted. First, to our knowledge, asymmetric k-center is the first problem that is hard to approximate to any constant factor in the worst case, yet can be optimally solved in polynomial time under perturbation resilience for a constant value of α. This is also the first tight result for any problem under perturbation resilience, i.e., this is the first time the exact value of α for which the problem switches from being NP-hard to efficiently computable has been found. Furthermore, our results illustrate a surprising relationship between symmetric and asymmetric k-center instances under perturbation resilience. Unlike approximation ratio, for which symmetric k-center is easily solved to a factor of 2 but asymmetric k-center cannot be approximated to any constant factor, both symmetric and asymmetric k-center can be solved optimally under resilience to 2-perturbations. Finally, our guarantees in the setting where only part of the data satisfies perturbation resilience make these algorithms more applicable to real-life instances.
DOI：
--
发表时间：
2017-12
期刊：
ArXiv
影响因子：
--
作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang
通讯作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang