English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The $k$-center problem is a canonical and long-studied facility location andclustering problem with many applications in both its symmetric and asymmetricforms. Both versions of the problem have tight approximation factors on worstcase instances. Therefore to improve on these ratios, one must go beyond theworst case.  In this work, we take this approach and provide strong positive results bothfor the asymmetric and symmetric $k$-center problems under a natural inputstability (promise) condition called $\alpha$-perturbation resilience [Bilu andLinia 2012], which states that the optimal solution does not change under anyalpha-factor perturbation to the input distances. We provide algorithms thatgive strong guarantees simultaneously for stable and non-stable instances: ouralgorithms always inherit the worst-case guarantees of clustering approximationalgorithms, and output the optimal solution if the input is $2$-perturbationresilient. 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 resultfor any problem under perturbation resilience. Furthermore, our resultsillustrate 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 andasymmetric $k$-center can be solved optimally under resilience to2-perturbations. Finally, our guarantees in the setting where only part of thedata satisfies perturbation resilience makes these algorithms more applicableto real-life instances.

$k$-center Clustering under Perturbation Resilience