# How to minimize the average distance between pumps and cities?

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?

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

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