k-center clustering under perturbation resilience

DOI10.4230/LIPICS.ICALP.2016.68MaRDI QIDQ4598207zbMATH OpenOpenAlexFDO

Authors Maria-Florina Balcan, Nika Haghtalab, Colin White

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1505.03924

zbMATH Keywords

\(k\)-center clusteringperturbation resilience

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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.

Recommendations

• \(k\)-center clustering under perturbation resilience
• scientific article; zbMATH DE number 7378621
• Algorithms for stable and perturbation-resilient problems

Cited in

(16)

• Resilient \(k\)-d trees: \(k\)-means in space revisited
• On perturbation resilience of non-uniform k-center
• Strategyproof facility location in perturbation stable instances
• Perturbation resilience for the facility location problem
• Asymmetric k -center is log ^* n -hard to approximate
• Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate
• scientific article; zbMATH DE number 6902592 (Why is no real title available?)
• Algorithms for stable and perturbation-resilient problems
• \(k\)-center clustering under perturbation resilience
• scientific article; zbMATH DE number 7378621 (Why is no real title available?)
• Bilu-Linial stability, certified algorithms and the independent set problem
• Stability and recovery for independence systems
• Mechanism design for perturbation stable combinatorial auctions
• scientific article; zbMATH DE number 7758333 (Why is no real title available?)
• Clustering under perturbation stability in near-linear time
• Exact algorithms and lower bounds for stable instances of Euclidean k-means

This page was built for publication: \(k\)-center clustering under perturbation resilience

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598207)