# NP-hardness of Euclidean k-Median for k = 2

In the Euclidean $$k$$-median problem, we are given a set $$C$$ of clients in $$\mathbb{R}^d$$. The task is to open a set $$F \subset \mathbb{R}^d$$ of $$k$$ facilities such that the cost function $$\Phi(F) = \sum_{x \in C} \min_{f \in F} \{ \|x-f\|_2 \}$$ is minimized.

It is known that the problem is $$\mathsf{NP}$$-hard for d = 2.

My question is: Is the problem $$\mathsf{NP}$$-hard for $$k = 2$$ (or some other constant)? Is it an open problem or is there is any known result?

I am aware that the Euclidean $$k$$-means problem is $$\mathsf{NP}$$-hard when d = 2 or k = 2.

• Do you know how to solve the problem for $d=2$ and $k=1$? Dec 15, 2021 at 16:19
• @Gamow No, I do not know. For $k=1$, the problem is known as the Fermat Weber problem. I am not sure about its NP-hardness too. I asked this question here before. Even if we could solve for $k = 1$ in polynomial time in the number of output bits; the problem for $k = 2$ is harder. Dec 15, 2021 at 16:40
• If you can solve the $k=1$ version, you also get the $k=2$ case. If there are two facilities $f_1$ and $f_2$, the clients that are closer to $f_1$ than to $f_2$ belong to a halfplane, and the remaining clients are closer to $f_2$ than to $f_1$. Hence you may simply check all partitions of the clients into two groups $G_1$ and $G_2$ by a halfplane (there is only a quadratic number $O(|C|^2)$ of such partitions), and determine with the $k=1$ subroutine the best facilities for $G_1$ and $G_2$. Dec 15, 2021 at 16:57
• @Gamow Okay Thanks. For $d = 2$ and $k = 2$ it is solvable then. For $d = 2$, there are indeed $O(|C|^2)$ partitions. But there can be exponential number of partitions for general $d$. My question is for general $d$ and $k = 2$. Dec 15, 2021 at 17:01
• @Gamow Consider a simplex in $d$ dimensional space. Then, there are $2^d$ possible partitions. Dec 15, 2021 at 17:06