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/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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

Zendy Tools

Zendy Open

We consider clustering in the perturbation resilience model that has beenstudied since the work of Bilu and Linial [ICS, 2010] and Awasthi, Blum andSheffet [Inf. Proc. Lett., 2012]. A clustering instance $I$ is said to be$\alpha$-perturbation resilient if the optimal solution does not change whenthe pairwise distances are modified by a factor of $\alpha$ and the perturbeddistances satisfy the metric property --- this is the metric perturbationresilience property introduced in Angelidakis et. al. [STOC, 2010] and a weakerrequirement than prior models. We make two high-level contributions.  1) We show that the natural LP relaxation of $k$-center and asymmetric$k$-center is integral for $2$-perturbation resilient instances. We belive thatdemonstrating the goodness of standard LP relaxations complements existingresults that are based on combinatorial algorithms designed for theperturbation model.  2) We define a simple new model of perturbation resilience for clusteringwith \emph{outliers}. Using this model we show that the unified MST and dynamicprogramming based algorithm proposed by Angelidakis et. al. [STOC, 2010]exactly solves the clustering with outliers problem for several common centerbased objectives (like $k$-center, $k$-means, $k$-median) when the instances is$2$-perturbation resilient. We further show that a natural LP relxation isintegral for $2$-perturbation resilient instances of \kcenter with outliers.

Perturbation Resilient Clustering for $k$-Center and Related Problems via LP Relaxations