<p>In the Euclidean <span class="math-container">$k$</span>-median problem, we are given a set <span class="math-container">$C$</span> of clients in <span class="math-container">$\mathbb{R}^d$</span>. The task is to open a set <span class="math-container">$F \subset \mathbb{R}^d$</span> of <span class="math-container">$k$</span> facilities such that the cost function <span class="math-container">$\Phi(F) = \sum_{x \in C} \min_{f \in F} \{ \|x-f\|_2 \}$</span> is minimized.</p>
<p>It is known that the problem is <span class="math-container">$\mathsf{NP}$</span>-hard for <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.2364&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">d = 2</a>.</p>
<p>My question is: Is the problem <span class="math-container">$\mathsf{NP}$</span>-hard for <span class="math-container">$k = 2$</span> (or some other constant)? Is it an open problem or is there is any known result?</p>
<hr />
<p>I am aware that the Euclidean <span class="math-container">$k$</span>-means problem is <span class="math-container">$\mathsf{NP}$</span>-hard when <a href="https://pdf.sciencedirectassets.com/271538/1-s2.0-S0304397512X00240/1-s2.0-S0304397510003269/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEI%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCIQCZ1%2BUNOsLwOpsRZ5uUz6L5tL7XG0%2BXy3lvjP%2BIZvGaTwIgIpqKuxBEWMxk6gAaFNCtD6osR4nyXmSeXXcrFG0Riewq%2BgMIeBAEGgwwNTkwMDM1NDY4NjUiDNITmEnZ8Ef5yJ2fwirXA08hOkmDXcUiqNZawA%2FbsY7z8S9sNLJPv97pQe1adRW%2Bi6oBesZBUx27nbIccxTUNcnol7FrcHLI8GD7%2FW8YGyhqCT00e0MaYJNugLKcyUmHsvkfF2Z6ohVN%2Beb8n1lurdob6r%2F%2FH8AzVVEiqWZMVxNlkXNwoG%2FjhKig6Ur64w%2FtIZiMDTLUwwC5%2ByY7mj92mMokmE6tjUAarDsQ5CsyU6LQ4IvwvV8rPLrhemjUt56XImKs1656xkNwK1BqCIu3mws9Ej9QT59ZFRkbgXV9WIHlbB8FeQZ%2FJQk%2B%2BCYcwOhaZL9tYgYzjP5IvJANtXu1lU84zcvMgoBEL09EJ6YK2dDDQdlXYLxyUMRnSA5thnW1%2FrDpb%2BA%2F36gaZK5ZDNt2qU3tkWG%2F7k4EfFnUPFHNT2tbT3u8NEYrcANmMrhs1a9K8mNku4TcKOZ9bmnb4oH%2Fyh61sVbkLt4OsJ8tfddFf9R%2F5zOuH%2FUFPElw%2Fk%2FLmzQIqELRQ3aVXHOIUvMDwXxlykF%2BeDhZpBbXmrdptOcEgiSa%2Fs2moTN8gGJgRRNx2rsAggfeaHUKUUbJiiA5sxQ2VKyUCgYEJYwvHYC1LWh5P3bBShMLAfxdr%2B8aTKwH%2B0OCBQCBwqcmxzDV%2BeeNBjqlAY80glRq6Id4QvEuXSogOh9uWp9i49JmCHfkmH8WNsKDrY6umY2klHMveHi7OO4v8SqCE%2FdHf7ERM7NMmvzjuKtVOleobXBHT8WbyYtuYfwl%2FSgs%2BS4sFbGgquaLon4110WCnuRos0Yh2jmyeslhIb5a2I6T9%2BBfLvyZWvkbrUUW%2F1vdiLdIZRoZK70Loa6QyxZCZrTSpVcuXjiZa1oAmHZ1a8dicw%3D%3D&amp;X-Amz-Algorithm=AWS4-HMAC-SHA256&amp;X-Amz-Date=20211215T153241Z&amp;X-Amz-SignedHeaders=host&amp;X-Amz-Expires=300&amp;X-Amz-Credential=ASIAQ3PHCVTY2FBA4YGG%2F20211215%2Fus-east-1%2Fs3%2Faws4_request&amp;X-Amz-Signature=c29fa0fe5595ab37538694a5b117e80952dd2c35ceb2aee2ca22047c09fa7d4f&amp;hash=1eb100d6abf3929d249b27f677e1d7544bd01dec4c01f0c4c9cc925950906d0c&amp;host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&amp;pii=S0304397510003269&amp;tid=spdf-15341fa9-a946-4f30-a11c-a33c5359015f&amp;sid=b569665b6f0ef64a34692dc9a3be37357f3cgxrqb&amp;type=client" rel="nofollow noreferrer">d = 2</a> or <a href="https://link.springer.com/content/pdf/10.1007/s10994-009-5103-0.pdf" rel="nofollow noreferrer">k = 2</a>.</p>

CC BY-SA 4.0
2021-12-15T16:19:41.070Z
Do you know how to solve the problem for $d=2$ and $k=1$?
Gamow
CC BY-SA 4.0
2021-12-15T16:40:38.993Z
@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](https://cstheory.stackexchange.com/questions/48557/is-the-fermat-weber-problem-mathsfnp-hard) 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.
Inuyasha Yagami
CC BY-SA 4.0
2021-12-15T16:57:54.033Z
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$.
Gamow
CC BY-SA 4.0
2021-12-15T17:01:46.690Z
@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$.
Inuyasha Yagami
CC BY-SA 4.0
2021-12-15T17:06:49.630Z
@Gamow Consider a simplex in $d$ dimensional space. Then, there are $2^d$ possible partitions.
Inuyasha Yagami
<reference-request><np-hardness><clustering>
NP-hardness of Euclidean k-Median for k = 2
Inuyasha Yagami
# NP-hardness of Euclidean k-Median for k = 2

(Asked by: username_0 on 2021-12-15)

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](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.2364&rep=rep1&type=pdf).

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](https://pdf.sciencedirectassets.com/271538/1-s2.0-S0304397512X00240/1-s2.0-S0304397510003269/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEI%2F%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCIQCZ1%2BUNOsLwOpsRZ5uUz6L5tL7XG0%2BXy3lvjP%2BIZvGaTwIgIpqKuxBEWMxk6gAaFNCtD6osR4nyXmSeXXcrFG0Riewq%2BgMIeBAEGgwwNTkwMDM1NDY4NjUiDNITmEnZ8Ef5yJ2fwirXA08hOkmDXcUiqNZawA%2FbsY7z8S9sNLJPv97pQe1adRW%2Bi6oBesZBUx27nbIccxTUNcnol7FrcHLI8GD7%2FW8YGyhqCT00e0MaYJNugLKcyUmHsvkfF2Z6ohVN%2Beb8n1lurdob6r%2F%2FH8AzVVEiqWZMVxNlkXNwoG%2FjhKig6Ur64w%2FtIZiMDTLUwwC5%2ByY7mj92mMokmE6tjUAarDsQ5CsyU6LQ4IvwvV8rPLrhemjUt56XImKs1656xkNwK1BqCIu3mws9Ej9QT59ZFRkbgXV9WIHlbB8FeQZ%2FJQk%2B%2BCYcwOhaZL9tYgYzjP5IvJANtXu1lU84zcvMgoBEL09EJ6YK2dDDQdlXYLxyUMRnSA5thnW1%2FrDpb%2BA%2F36gaZK5ZDNt2qU3tkWG%2F7k4EfFnUPFHNT2tbT3u8NEYrcANmMrhs1a9K8mNku4TcKOZ9bmnb4oH%2Fyh61sVbkLt4OsJ8tfddFf9R%2F5zOuH%2FUFPElw%2Fk%2FLmzQIqELRQ3aVXHOIUvMDwXxlykF%2BeDhZpBbXmrdptOcEgiSa%2Fs2moTN8gGJgRRNx2rsAggfeaHUKUUbJiiA5sxQ2VKyUCgYEJYwvHYC1LWh5P3bBShMLAfxdr%2B8aTKwH%2B0OCBQCBwqcmxzDV%2BeeNBjqlAY80glRq6Id4QvEuXSogOh9uWp9i49JmCHfkmH8WNsKDrY6umY2klHMveHi7OO4v8SqCE%2FdHf7ERM7NMmvzjuKtVOleobXBHT8WbyYtuYfwl%2FSgs%2BS4sFbGgquaLon4110WCnuRos0Yh2jmyeslhIb5a2I6T9%2BBfLvyZWvkbrUUW%2F1vdiLdIZRoZK70Loa6QyxZCZrTSpVcuXjiZa1oAmHZ1a8dicw%3D%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20211215T153241Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTY2FBA4YGG%2F20211215%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=c29fa0fe5595ab37538694a5b117e80952dd2c35ceb2aee2ca22047c09fa7d4f&hash=1eb100d6abf3929d249b27f677e1d7544bd01dec4c01f0c4c9cc925950906d0c&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S0304397510003269&tid=spdf-15341fa9-a946-4f30-a11c-a33c5359015f&sid=b569665b6f0ef64a34692dc9a3be37357f3cgxrqb&type=client) or [k = 2](https://link.springer.com/content/pdf/10.1007/s10994-009-5103-0.pdf).

**Tags:** reference-request, np-hardness, clustering
> **Comments:**
> **username_1**: Do you know how to solve the problem for $d=2$ and $k=1$?  
> **username_0**: @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](https://cstheory.stackexchange.com/questions/48557/is-the-fermat-weber-problem-mathsfnp-hard) 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.  
> **username_1**: 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$.  
> **username_0**: @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$.  
> **username_0**: @Gamow Consider a simplex in $d$ dimensional space. Then, there are $2^d$ possible partitions.  

---

## 0 answers

