There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k cities. The cities are all in a straight line.

How do I need to install these so that the average distance between the cities and the nearest pumps is minimized?

What I am thinking is that dividing is this:

Suppose there are 6 cities [C1, C2, C3, C4, C5, C6] and 3 pumps [P1, P2, P3].

I divide the array of cities equally -> [C1, C2] , [C2, C3] .. and then each block gets one pump.

Then again break that [C1,C2] and let C2 have the pump. Same way C4 and C6.

So basically recursively calling and assigning the city a pump. Is this the right way to approach this problem?

  • $\begingroup$ It doesn't take into account that some cities are close together and some are not. $\endgroup$ – gnasher729 Dec 9 '18 at 10:07
  • $\begingroup$ @gnasher729 Yes, did not think about that. $\endgroup$ – Pritam Banerjee Dec 9 '18 at 10:09
  • $\begingroup$ @gnasher729 Should it be then solved like a kmeans algorithm? $\endgroup$ – Pritam Banerjee Dec 9 '18 at 10:10

Minimizing the average distance is equivalent to minimizing the sum of the distances, so let me work with that formulation of the problem.

Hint #1: When $k = 1$, the pump should be located at the median of the positions of the cities.

Hint #2: When $k > 1$, you can use a dynamic programming approach. Let $f(i, j)$ be the optimal cost of serving cities $1,...,i$ with $j$ pumps. Your goal is to compute $f(n, k)$. Now observe that $$ f(n,k) = \min_{i=1,...,n} \left( \sum_{i': i < i' \le n} d(\text{city}_{i'}, \text{pump}_k) + f(i,k-1) \right), $$ because if the rightmost pump (pump number $k$) serves cities $i+1$ through $n$, then the total cost is the sum of distances of those cities to pump $k$, plus the optimal cost of serving cities $1$ through $i$ with $k-1$ pumps. Here $\text{pump}_k$ is the position at the median of cities $i+1,...,n$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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