We investigate the complexity of solving stable or perturbation-resilient instances of k-means and kmedian 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, Blum, and Sheffet [2012] . In our context, we say a k-means instance is α-stable if there is a unique optimum solution which remains unchanged if distances are (non-uniformly) stretched by a factor of at most α. 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 ǫ > 0, (1 + ǫ)-stable instances of k-means in doubling metrics, which include fixed-dimensional Euclidean metrics, can be solved in polynomial time. More precisely, we show a natural multi-swap local-search algorithm in fact finds the optimum solution for (1 + ǫ)-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 ǫ0 > 0 such there is not even a PTAS for (1 + ǫ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, Goldreich, and Gur have already shown stable QSAT is hard to approximation for some constant Q [16], our hypothesis is simply that stable QSAT with bounded variable occurrence is also hard (there is in fact work in progress to prove this hypothesis). Given this hypothesis, we consider "stability-preserving" reductions to prove our hardness for stable k-means. Such reductions seem to be more fragile and intricate than standard L-reductions and may be of further use to demonstrate other stable optimization problems are hard to solve.
Independent and concurrent to this work, Friggstad et al. REF showed that for any fixed d 1 and α > 1, α-multiplicative perturbation resilient instances of discrete k-means and k-median (where the centers must be from the data-points themselves) in metrics with doubling dimension d can be solved in time O n d O(d) (α−1) −O(d/(α−1)) k .
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
ArXiv
ArXiv
Computer Science Mathematics