2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – Inuyasha Yagami
    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$
    – Inuyasha Yagami
    Dec 15, 2021 at 17:01
  • 2
    $\begingroup$ @Gamow Consider a simplex in $d$ dimensional space. Then, there are $2^d$ possible partitions. $\endgroup$
    – Inuyasha Yagami
    Dec 15, 2021 at 17:06

0

Reset to default

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.