  We investigate the fine-grained complexity of approximating the classical
$k$-median / $k$-means clustering problems in general metric spaces. We show
how to improve the approximation factors to $(1+2/e+\varepsilon)$ and
$(1+8/e+\varepsilon)$ respectively, using algorithms that run in
fixed-parameter time. Moreover, we show that we cannot do better in FPT time,
modulo recent complexity-theoretic conjectures.
