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, 2018 at 10:07
  • $\begingroup$ @gnasher729 Yes, did not think about that. $\endgroup$ Dec 9, 2018 at 10:09
  • $\begingroup$ @gnasher729 Should it be then solved like a kmeans algorithm? $\endgroup$ Dec 9, 2018 at 10:10

1 Answer 1


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 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.