Symmetric and Asymmetric k-center Clustering under Stability

Опубликовано 21 июня 2016, 23:44

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 a log*(n)-approximation for the asymmetric version. Therefore, to improve on these guarantees, one must go beyond the worst case and consider the instances that satisfy some natural structural properties. In this talk, I will describe strong positive results in this direction, showing how natural input stability (promise) conditions can be leveraged to provide substantially stronger results. We consider the alpha-perturbation resilience notion of Bilu and Linial [BL12], which states that the optimal solution does not change under any alpha-factor perturbation to the input distances. Our results show that by merely assuming 3-perturbation resilience, the exact solution for the asymmetric k-center problem can be found in polynomial time. For the case of symmetric k-center, we give an efficient algorithm to cluster 2-perturbation resilient instances, and we show that this is tight by proving that (2-epsilon)-perturbation resilience is hard unless NP=RP. We also consider the (alpha, epsilon)-approximation stability notion of Balcan et al. [BBG09] and provide additional tight positive results. Our results illustrate a surprising relation between symmetric and asymmetric k-center instances under these stability conditions. 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 small constant-factor perturbations. This talk is based on joint work with Nina Balcan and Colin White.