Abstract
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. Therefore to improve on these ratios, one must go beyond the worst case. In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric $k$-center problems under a natural input stability (promise) condition called $\alpha$-perturbation resilience [Bilu and Linia 2012], which states that the optimal solution does not change under any alpha-factor perturbation to the input distances. We provide algorithms that give strong guarantees simultaneously for stable and non-stable instances: our algorithms always inherit the worst-case guarantees of clustering approximation algorithms, and output the optimal solution if the input is $2$-perturbation resilient. Furthermore, we prove our result is tight by showing symmetric $k$-center under $(2-\epsilon)$-perturbation resilience is hard unless $NP=RP$. The impact of our results are multifaceted. This is the first tight result for any problem under perturbation resilience. Furthermore, our results illustrate a surprising relationship between symmetric and asymmetric $k$-center instances under perturbation resilience. 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 2-perturbations. Finally, our guarantees in the setting where only part of the data satisfies perturbation resilience makes these algorithms more applicable to real-life instances.
Introduction: Beyond Worst-Case Clustering
Clustering is a fundamental task in data science: given a set of points, the goal is to group them such that points within the same group are "close" and points in different groups are "far." The $k$-center problem specifically aims to find $k$ centers such that the maximum distance from any point to its nearest center is minimized.
In worst-case analysis, this problem is notoriously difficult. For symmetric distances (where $d(a,b) = d(b,a)$), the best possible approximation factor is 2. For asymmetric distances, the situation is even more challenging, with the best algorithms only achieving an $O(\log^* k)$ factor. However, real-world data often possesses inherent structure that worst-case analysis fails to capture. This paper utilizes perturbation resilience, a "beyond worst-case" framework, to explore these structures. An instance is $\alpha$-perturbation resilient if the optimal clustering remains unchanged even if any distance is scaled by a factor up to $\alpha$. The central question is: how much stability is required to solve this NP-hard problem optimally?
Methodology: Robust Algorithms and Local Stability
The authors develop several algorithmic strategies to bridge the gap between stability and worst-case performance:
- Robust Algorithms: They design algorithms that provide a "best of both worlds" guarantee. If the data is 2-perturbation resilient, the algorithm finds the exact optimal clustering. If the data is not stable, the algorithm still maintains the best-known worst-case approximation ratios.
- The Symmetrized Set: To handle the asymmetric case, they introduce a technique to identify a "symmetrized set" of points that behave like symmetric data, followed by a pruning process to isolate true cluster centers.
- Local Stability: Recognizing that entire datasets are rarely perfectly stable, the authors extend their theory to "local" perturbation resilience. They show that if only a specific region of the data is stable, their algorithms can correctly identify optimal clusters in that region while approximating the rest.
- Parsimonious Reductions: To prove the tightness of their results, they employ complex mathematical reductions to show that solving the problem with a stability factor of $2-\epsilon$ remains NP-hard.
Key Insights: The Phase Transition at $\alpha=2$
- The Magic Number: The most striking finding is a sharp phase transition at $\alpha=2$. At this threshold, the problem becomes solvable in polynomial time, whereas at $\alpha = 1.99$, it remains NP-hard. This represents the first tight result for any problem under the perturbation resilience framework.
- Asymmetric Equality: While asymmetric $k$-center is much harder than symmetric in the worst case, they are equally "easy" to solve optimally under 2-perturbation resilience. This suggests that stability acts as a powerful equalizer across different problem variants.
- Graceful Degradation: Unlike many stable algorithms that fail if the data is slightly noisy, the authors' "local stability" approach allows for success on clean sub-regions of a dataset even if the global instance is not perfectly stable.
- Optimality of Simple Heuristics: The authors prove that for symmetric $k$-center, standard 2-approximation algorithms (such as Gonzalez's algorithm) are already "stability-optimal," naturally finding the ground truth if the data is 2-perturbation resilient.
Key Results
The paper establishes several definitive bounds for $k$-center clustering under various stability conditions, as summarized in the table below.
- Optimality: Both symmetric and asymmetric $k$-center are solvable optimally in polynomial time under 2-perturbation resilience.
- Hardness: Symmetric $k$-center is NP-hard to solve under $(2-\epsilon)$-perturbation resilience for any $\epsilon > 0$.
- Local Guarantees: The proposed asymmetric $k$-center algorithm achieves an $O(\log^* n)$ approximation in the worst case but extracts optimal clusters from any 2-perturbation resilient sub-region.
- Metric Resilience: The results are robust enough to hold under "metric perturbation resilience," where distances must still satisfy the triangle inequality after perturbation.
Conclusion and Future Directions
While this work provides a complete understanding of $k$-center under perturbation resilience, several avenues for future research remain. For the more relaxed $(\alpha, \epsilon)$-perturbation resilience (where a small fraction of points may shift), current results require a lower bound on cluster size ($|C_i| > 2\epsilon n$). Removing this constraint is an open challenge. Additionally, while $k$-center is now well-characterized, other objectives like $k$-median or $k$-means lack similarly tight results. Finally, developing more "verifiable" stability conditions that can be checked efficiently on real-world datasets remains a priority for making these theoretical guarantees more practically applicable.
Summary updated