  The $k$-Median problem is one of the well-known optimization problems that
formalize the task of data clustering. Here, we are given sets of facilities
$F$ and clients $C$, and the goal is to open $k$ facilities from the set $F$,
which provides the best division into clusters, that is, the sum of distances
from each client to the closest open facility is minimized. In the Capacitated
$k$-Median, the facilities are also assigned capacities specifying how many
clients can be served by each facility.
  Both problems have been extensively studied from the perspective of
approximation algorithms. Recently, several surprising results have come from
the area of parameterized complexity, which provided better approximation
factors via algorithms with running times of the form $f(k)\cdot poly(n)$. In
this work, we extend this line of research by studying a different choice of
parameterization. We consider the parameter $\ell = |F| - k$, that is, the
number of facilities that remain closed. It turns out that such a
parameterization reveals yet another behavior of $k$-Median. We observe that
the problem is W[1]-hard but it admits a parameterized approximation scheme.
Namely, we present an algorithm with running time
$2^{O(\ell\log(\ell/\epsilon))}\cdot poly(n)$ that achieves a
$(1+\epsilon)$-approximation. On the other hand, we show that under the
assumption of Gap Exponential Time Hypothesis, one cannot extend this result to
the capacitated version of the problem.
