Abstract
The kcenter problem is a canonical and longstudied 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: a 2approximation for symmetric kcenter and an O(log*(k))approximation for the asymmetric version. 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 kcenter problems under a very natural input stability (promise) condition called alphaperturbation resilience [Bilu Linial, 2012], which states that the optimal solution does not change under any alphafactor perturbation to the input distances. We show that by assuming 2perturbation resilience, the exact solution for the asymmetric kcenter problem can be found in polynomial time. To our knowledge, this is the first problem that is hard to approximate to any constant factor in the worst case, yet can be optimally solved in polynomial time under perturbation resilience for a constant value of alpha. Furthermore, we prove our result is tight by showing symmetric kcenter under (2epsilon)perturbation resilience is hard unless NP=RP.
This is the first tight result for any problem under perturbation resilience, i.e., this is the first time the exact value of alpha for which the problem switches from being NPhard to efficiently computable has been found.
Our results illustrate a surprising relationship between symmetric and asymmetric kcenter instances under perturbation resilience. Unlike approximation ratio, for which symmetric kcenter is easily solved to a factor of 2 but asymmetric kcenter cannot be approximated to any constant factor, both symmetric and asymmetric kcenter can be solved optimally under resilience
to 2perturbations.
BibTeX  Entry
@InProceedings{balcan_et_al:LIPIcs:2016:6216,
author = {MariaFlorina Balcan and Nika Haghtalab and Colin White},
title = {{kCenter Clustering Under Perturbation Resilience}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {68:168:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6216},
URN = {urn:nbn:de:0030drops62160},
doi = {10.4230/LIPIcs.ICALP.2016.68},
annote = {Keywords: kcenter, clustering, perturbation resilience}
}
Keywords: 

kcenter, clustering, perturbation resilience 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 
Issue Date: 

2016 
Date of publication: 

17.08.2016 