  We study the complexity of the classic capacitated k-median and k-means
problems parameterized by the number of centers, k. These problems are
notoriously difficult since the best known approximation bound for high
dimensional Euclidean space and general metric space is $\Theta(\log k)$ and it
remains a major open problem whether a constant factor exists. We show that
there exists a $(3+\epsilon)$-approximation algorithm for the capacitated
k-median and a $(9+\epsilon)$-approximation algorithm for the capacitated
k-means problem in general metric spaces whose running times are $f(\epsilon,k)
n^{O(1)}$. For Euclidean inputs of arbitrary dimension, we give a
$(1+\epsilon)$-approximation algorithm for both problems with a similar running
time. This is a significant improvement over the $(7+\epsilon)$-approximation
of Adamczyk et al. for k-median in general metric spaces and the
$(69+\epsilon)$-approximation of Xu et al. for Euclidean k-means.
