Dynamic programming algorithm for facility locations

Question

There are n houses at locations a_1, a_2,..., a_n along a line. We want to set up porta potties along that same line so that every house is within distance R of at least one porta potty. These porta potties are restricted to the specified locations b_1, b_2,..., b_m. Let c_i be the cost of setting up a porta potty at location b_i.

Find a dynamic programming algorithm that minimizes the total cost of setting up the porta potties. The algorithm should be able to detect if a solution does not exist. Assume that all a and b values are distinct.

Inputs:

• A[1, 2,...n] holds the house locations

• B[1, 2,...m] holds the potential porta potty locations

• C[1, 2,...m] holds the cost of setting up a porta potty at each location

Output: the minimum cost of placing the porta potties under the constraint that every house must be within distance R of some porta potty

I'm having trouble figuring out a recursive expression to work off of. Any help would be appreciated!

Answer 1

Your question gave me the chance to write some code for a similar problem which often appears as cellphone tower placing problem or cellphone base coverage problem.

Pseudocode follows:

1) Sort houses in ascending order
2) Sort facilities positions and their costs in ascending order by facilities positions
3) Let dp(i) be the minimum cost to cover i houses and lastBase(j) the last base used to cover j houses
4) Set the base case dp(0) = 0 and lastBase(0) = -1
5) For each house i:
6)   Check if previous solution is either valid or in range of this new house
7)   if it is -> grab it as solution
8)   else
9)     find a new base starting from lastBase(i) + 1 which can cover this house
10)    let it be the minimum-cost one
11)  if a base could be found -> add it to the previous solution
12)  else -> Problem cannot be solved

I recommend trying it out yourself first.

For completeness' sake: explanation, images and C++ code are available here.

Feedback or errors are welcome.