Resilient k-Clustering

摘要

We study the problem of resilient clustering in the metric setting where one is interested in designing algorithms that return high quality solutions that preserve the clustering structure under perturbations of the input points. Our first contribution is to introduce a formal notion of algorithmic resiliency for clustering problems that, roughly speaking, requires an algorithm to have similar outputs on close inputs. Then, we notice that classic algorithms have weak resiliency guarantees and develop new algorithms for fundamental clustering problems such as k-center, k-median, and k-means. Finally, we complement our results with an experimental analysis showing the effectiveness of our techniques on real-world instances.