  The Non-Uniform $k$-center (NUkC) problem has recently been formulated by
Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the
classical $k$-center clustering problem. In NUkC, given a set of $n$ points $P$
in a metric space and non-negative numbers $r_1, r_2, \ldots , r_k$, the goal
is to find the minimum dilation $\alpha$ and to choose $k$ balls centered at
the points of $P$ with radius $\alpha\cdot r_i$ for $1\le i\le k$, such that
all points of $P$ are contained in the union of the chosen balls. They showed
that the problem is NP-hard to approximate within any factor even in tree
metrics. On the other hand, they designed a "bi-criteria" constant
approximation algorithm that uses a constant times $k$ balls. Surprisingly, no
true approximation is known even in the special case when the $r_i$'s belong to
a fixed set of size 3. In this paper, we study the NUkC problem under
perturbation resilience, which was introduced by Bilu and Linial
[Combinatorics, Probability and Computing, 2012]. We show that the problem
under 2-perturbation resilience is polynomial time solvable when the $r_i$'s
belong to a constant sized set. However, we show that perturbation resilience
does not help in the general case. In particular, our findings imply that even
with perturbation resilience one cannot hope to find any "good" approximation
for the problem.
