Placing K gas stations among n cities to minimize distance

Question

There are $n$ cities on a highway with coordinates $x_1$ , . . . , $x_n$ and we aim to build $K < n$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and we hope to minimize the average distance from each city to the closest gas station. Please give an algorithm to compute the optimal way to place these $K$ gas stations. The algorithm should run in $O(n^2K)$ time.

I brute forced the answer by finding every single possible placement of gas stations and returning the minimum combo. Then I spent way too long fiddling with different ideas in Python to try and reduce the big-$O$ notation to no avail. Eventually I found a thread on the subject, but the formula isn't working for me.

How to minimize the average distance between pumps and cities?

I tried replicating the formula given in this thread in Python and it just doesn't work. It comes close but no dice. Here's my code (assume "cities" is the list of cities):

def f(n, k):
    if k == 1: # if k is 1, return total distance from the cities to the median 
        pump = n // 2
        return sum([abs(loc - cities[pump]) for loc in cities[:n]])

    min_list = []
    for i in range(n-1):
        sum_list = []
        for j in range(i+1, n):
            pumpk = ((j + 1) + (n-1)) // 2 
            sum_list.append(abs(cities[j] - cities[pumpk]) + f(i, k-1))
        min_list.append(sum(sum_list))
    return min(min_list)

I'm at such a loss! How can I solve the problem with the required time-complexity?

Answer 1

It looks that the recurrence relation is not implemented correctly in the code given in the question.

---

Here is a correct implementation.

# `cities` is a list of increasing integers that gives the
# locations of all cities such as follows
cities = [1, 5, 20, 22, 40, 100, 110]
K = 2


def min_sum_distances(start, end):
  """ Cities between `start` inclusive and `end` exclusive. One pump is installed."""
  pump_loc = start + end >> 1
  return sum(abs(city - cities[pump_loc]) for city in cities[start:end])


def min_sum(total_pumps):
  n = len(cities)

  # `dp[c][p]` is the minimum sum of distances from the first `c` cities
  # to the nearest pump when `p` pumps are installed.
  # 1 <= c <= n and 1 <= p <= K
  dp = [[float("infinity")] * (K + 1) for number_of_pumps in range(n + 1)]
  for c in range(1, n + 1):
    dp[c][1] = min_sum_distances(0, c)
    for p in range(2, min(c + 1, total_pumps + 1)):
      for cities_covered_before in range(p - 1, c):
        dp[c][p] = min(dp[c][p], dp[cities_covered_before][p - 1]
            + min_sum_distances(cities_covered_before, n))
return dp[n][total_pumps]


print(min_sum(K) / len(cities))
# 9.42857142857

The implementation runs in $O(n^3K)$ time.

---

In order to spend up the performance, we can reimplement min_sum_distance so that it runs in $O(1)$ instead of $O(n)$. We can use precomputed prefix sums of cities.

from itertools import accumulate
pre_sums = list(accumulate(cities, initial=0))

def min_sum_distances(start, end):
  pump_loc = start + end >> 1
  return pre_sums[start] + pre_sums[end] - 2 * pre_sums[pump_loc] \
      - (cities[pump_loc] if (end - start) & 1 else 0)

With the improvement, the implementation runs in $O(n^2K)$ time.