# A facility location problem

Consider the following scenario. There are N localities in a town where population for locality $L_i$ is denoted by $P_i$, $i \in {1,\ldots,n}$. We need to place K hospitals around the town in a way that the cost of accessing the hospital is minimized.

We are basically trying to $$\min_O(\sum_{i=1}^N P_i \times C(d(L_i,O(L_i))))$$ where, $$O(L_i) = \textrm{Nearest hospital's location to }L_i\\d=\textrm{Euclidean distance between 2 locations}\\C = \textrm{Cost function to travel distance }d"$$

It doesn't seem we can use gradient descent. Consider 3 localities $L_1,L_2$ and $L_3$ and 2 hospitals $H_1,H_2$. If we initially put $H_1,H_2$ on $L_1,L_2$ e.g.

$$L_1H_1\ldots L_2H_2 \ldots L_3$$

If the gradient descent starts moving projects to the right, then we may find ourselves in the following situation. The final location of nearest hospital to $L_2$ would have changed from $H_2$ to $H_1$.

$$L_1\ldots H_1L_2 \ldots H_2L_3$$

So could you please give me some pointers on how to solve this problem?

• If $K \geq N$ then can't you just take $H_i = L_i$, that is, collocate the hospitals with the towns? – Yuval Filmus Feb 3 '16 at 12:55
• True. Now as an extension consider $K$ to denote not just hospitals but different kinds of projects. So for the rest $K-N$ projects do you run a greedy algorithm based on population in those cities? – Sandipan Bhattacharyya Feb 3 '16 at 13:06
• If $K>N$ then the other $K-N$ hospitals you can put wherever you wish. It won't change your objective function. If you have a different objective function in mind, you have to let us know. – Yuval Filmus Feb 3 '16 at 13:08
• Ok. Sorry my mistake. The objective function is as has been stated. – Sandipan Bhattacharyya Feb 3 '16 at 13:12
• Please edit the question to clear up any confusion for future readers from the top. Then, we can remove these comments. – Raphael Feb 3 '16 at 16:22

This problem is known as Euclidean $k$-center problem and is known to be NP-complete. There are some approximation algorithms but we don't have any PTAS algorithm.

Of course for $K \geq N$, the solution is trivial, with optimal value 0.