Tight FPT Approximations for $k$-Median and $k$-Means

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\mathrm{/}e+\epsilon )$ and $(1+8\mathrm{/}e+\epsilon )$ 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.