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.

  • $\begingroup$ Do you know how to solve the problem for $d=2$ and $k=1$? $\endgroup$
    – Gamow
    Dec 15, 2021 at 16:19
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 15, 2021 at 16:40
  • $\begingroup$ 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$. $\endgroup$
    – Gamow
    Dec 15, 2021 at 16:57
  • $\begingroup$ @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$. $\endgroup$ Dec 15, 2021 at 17:01
  • 2
    $\begingroup$ @Gamow Consider a simplex in $d$ dimensional space. Then, there are $2^d$ possible partitions. $\endgroup$ Dec 15, 2021 at 17:06


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.