There are n cities [1, 2, 3, .... n] and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to the closest hospitals.?

Right now my thought is using dynamic programming with a 2D array of size n * k. Then I know optimal solution will be f(n, k) = enter image description here, which pump𝑘 is the position at the median of cities 𝑖+1,...,𝑛. I believe this is the right approach but I do not know how to store the location of each hospitals. Please help

New contributor
noname is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • $\begingroup$ Just to check if I am understanding your problem correctly, Is your problem equivalent to minimizing the sum of the distances of each city to the closest hospital? $\endgroup$ – Inuyasha Yagami Jun 9 at 3:19
  • $\begingroup$ @InuyashaYagami Yes!!! $\endgroup$ – noname Jun 9 at 3:41
  • 1
    $\begingroup$ First, note that the problem is called the $k$-median problem which NP-hard. So, you can not expect any algorithm with a running time polynomial in $n$ and $k$ $\endgroup$ – Inuyasha Yagami Jun 9 at 3:43
  • $\begingroup$ @InuyashaYagami Hi, I believe my run time will be n^2k. the n * k is just the 2d array for me to build up the final solution $\endgroup$ – noname Jun 9 at 3:46
  • $\begingroup$ Secondly, what do you mean by the median of the cities? Is it $1$-median. In that case, $pump_{k}$ might not be located at some city. $\endgroup$ – Inuyasha Yagami Jun 9 at 3:46

Your Answer

noname is a new contributor. Be nice, and check out our Code of Conduct.

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

Browse other questions tagged or ask your own question.