The continuous Euclidean $k$-means problem is defined as follows:

Given a set $X$ of $n$ points in $d$ dimensional Euclidean space $\mathbb{R}^{d}$. Given a parameter $k>0$, find a partitioning $P$ of $X$ into sets $X_1,\dotsc,X_k$ such that the following clustering cost is minimized:

$$\Phi(P) = \sum_{i = 1}^{k} \sum_{x \in X_i} \|x - \mu(X_i)\|^{2}, \quad \textrm{where $\mu(X_{i})$ is the centroid of $X_i$.}$$

For constant $k$, the problem is $\mathsf{NP}$-hard (see here).

For constant $d$, the problem is $\mathsf{NP}$-hard (see here).

What about when both $k$ and $d$ are constant? Well, there is an $O(n^{kd})$ algorithm for the problem (see here). But is there any exact $\mathsf{FPT}$ algorithm known for the problem with running time $f(k,d) \cdot n^{O(1)}$ or any related $\mathsf{FPT}$ hardness result known?

Note: I know that discrete metric $k$-means problem is $\mathsf{W}[2]$-hard, parametrized by $k$ (see here). But it does not imply $\mathsf{FPT}$ hardness for the continuous Euclidean space.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.