3
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.