Parameterized k-Clustering: The distance matters!

We consider the $k$-Clustering problem, which is for a given multiset of $n$ vectors $X\subset {\mathbb{Z}}^d$ and a nonnegative number $D$, to decide whether $X$ can be partitioned into $k$ clusters $C_1,\dots ,C_k$ such that the cost $$\sum _{i=1}^k\underset{c_i\in {\mathbb{R}}^d}{\min }\sum _{x\in C_i}\mathrm{\parallel }x-c_i{\mathrm{\parallel }}_p^p\le D,$$ where $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_p$ is the Minkowski ($L_p$) norm of order $p$. For $p=1$, $k$-Clustering is the well-known $k$-Median. For $p=2$, the case of the Euclidean distance, $k$-Clustering is $k$-Means. We show that the parameterized complexity of $k$-Clustering strongly depends on the distance order $p$. In particular, we prove that for every $p\in (0,1]$, $k$-Clustering is solvable in time $2^{O(D\log D)}(nd{)}^{O(1)}$, and hence is fixed-parameter tractable when parameterized by $D$. On the other hand, we prove that for distances of orders $p=0$ and $p=\mathrm{\infty }$, no such algorithm exists, unless FPT=W[1].