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 ratios, one must go beyond the worst case. In this talk, I will describe strong positive results in this direction, showing how a natural input stability (promise) condition called perturbation resilience, which states that the optimal solution does not change under any alpha-factor perturbation to the input distances, can be leveraged to provide substantially stronger results.
We 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 this result is tight by showing (2-epsilon)-perturbation resilience is hard unless NP=RP.
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 is joint work with Nina Balcan and Nika Haghtalab.