3
$\begingroup$

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?

$\endgroup$
5
  • 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$ Commented Feb 3, 2016 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$ Commented Feb 3, 2016 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$ Commented Feb 3, 2016 at 13:08
  • $\begingroup$ Ok. Sorry my mistake. The objective function is as has been stated. $\endgroup$ Commented Feb 3, 2016 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
    Commented Feb 3, 2016 at 16:22

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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