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?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ If $K \geq N$ then can't you just take $H_i = L_i$, that is, collocate the hospitals with the towns? $\endgroup$ – Yuval Filmus Feb 3 '16 at 12:55
  • $\begingroup$ 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? $\endgroup$ – Sandipan Bhattacharyya Feb 3 '16 at 13:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 3 '16 at 13:08
  • $\begingroup$ Ok. Sorry my mistake. The objective function is as has been stated. $\endgroup$ – Sandipan Bhattacharyya Feb 3 '16 at 13:12
  • 1
    $\begingroup$ Please edit the question to clear up any confusion for future readers from the top. Then, we can remove these comments. $\endgroup$ – 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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.