Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
复制标题
欧几里得 k 均值稳定实例的精确算法和下界
DOI：
10.1137/1.9781611975482.183
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Salavatipour
中科院分区：
文献类型：
--
作者：
Zachary Friggstad;K. Khodamoradi;M. Salavatipour
我们研究了在固定尺寸欧几里得指标中求解k-均值和k-median聚类的稳定或扰动 - 弹性实例的复杂性（或更一般而言的指标）。 Bilu和Linial [2010]和Awasthi等人引入了稳定或扰动弹性实例的概念。 [2012]。在我们的上下文中，我们说，如果有唯一的OPT解决方案，如果距离（不均匀）伸展至最多\ alpha，则K-均值实例是\ alpha稳定的。已经研究了稳定的聚类实例，以解释为什么诸如劳埃德算法之类的启发式方法在实践中表现良好。在这项工作中，我们表明，对于任何固定的\ epsilon> 0（1+ \ epsilon） - 在多项式时间内可以解决二倍指标中k均值的稳定实例。更准确地说，我们显示出一种天然的多局部局部搜索算法实际上是在多项式迭代中找到了K-Means和K-Median的稳定实例的OPT解决方案。我们通过证明在合理的PCP假设下进行补充，这基本上是紧密的：当尺寸D是输入的一部分时，就会有一个固定的\ epsilon_0> 0 s.t.除非np = rp，否则（1+ \ epsilon_0） - 稳定的k-means甚至没有PTA。为此，我们考虑了CSP的强大财产；如果存在唯一的最佳解决方案X^*，并且对于任何其他解决方案X'，请调用一个稳定的实例，则不满意的子句的数量与X^*和X'之间的锤距距离成正比。 Dinur等。对于某些常数Q，很难显示稳定的QSAT很难近似，我们的假设仅仅是稳定的QSAT也很难。鉴于这一假设，我们考虑“稳定性”的减少，以证明我们对稳定K-均值的硬度。这种减少似乎比标准L还原更脆弱，并且可能进一步证明其他稳定的优化问题很困难。
We investigate the complexity of solving stable or perturbation-resilient instances of k-Means and k-Median clustering in fixed dimension Euclidean metrics (or more generally doubling metrics). The notion of stable or perturbation resilient instances was introduced by Bilu and Linial [2010] and Awasthi et al. [2012]. In our context we say a k-Means instance is \alpha-stable if there is a unique OPT solution which remains unchanged if distances are (non-uniformly) stretched by a factor of at most \alpha. Stable clustering instances have been studied to explain why heuristics such as Lloyd's algorithm perform well in practice. In this work we show that for any fixed \epsilon>0, (1+\epsilon)-stable instances of k-Means in doubling metrics can be solved in polynomial time. More precisely we show a natural multiswap local search algorithm in fact finds the OPT solution for (1+\epsilon)-stable instances of k-Means and k-Median in a polynomial number of iterations. We complement this result by showing that under a plausible PCP hypothesis this is essentially tight: that when the dimension d is part of the input, there is a fixed \epsilon_0>0 s.t. there is not even a PTAS for (1+\epsilon_0)-stable k-Means in R^d unless NP=RP. To do this, we consider a robust property of CSPs; call an instance stable if there is a unique optimum solution x^* and for any other solution x', the number of unsatisfied clauses is proportional to the Hamming distance between x^* and x'. Dinur et al. have already shown stable QSAT is hard to approximate for some constant Q, our hypothesis is simply that stable QSAT with bounded variable occurrence is also hard. Given this hypothesis, we consider "stability-preserving" reductions to prove our hardness for stable k-Means. Such reductions seem to be more fragile than standard L-reductions and may be of further use to demonstrate other stable optimization problems are hard.
DOI：
--
发表时间：
2017-12
期刊：
ArXiv
影响因子：
--
作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang
通讯作者：
Aravindan Vijayaraghavan;Abhratanu Dutta;Alex L. Wang