Suppose you’re running a lightweight consulting business—just you, two associates, and some rented equipment. Your clients are distributed between the East Coast and the West Coast, and this leads to the following question.

Each month, you can either run your business from an office in New York (NY) or from an office in San Francisco (SF). In month i, you’ll incur an operating cost of Ni if you run the business out of NY; you’ll incur an operating cost of S_i if you run the business out of SF. (It depends on the distribution of client demands for that month.)

However, if you run the business out of one city in month i, and then out of the other city in month i + 1, then you incur a fixed moving cost of M to switch base offices.

Given a sequence of n months, a plan is a sequence of n locations— each one equal to either NY or SF—such that the i^th location indicates the city in which you will be based in the i^th month. The cost of a plan is the sum of the operating costs for each of the n months, plus a moving cost of M for each time you switch cities. The plan can begin in either city.

The problem.

Given a value for the moving cost M, and sequences of operating costs N₁,..., N_n and S₁,..., S_n, find a plan of minimum cost. (Such a plan will be called optimal.)

Example. Suppose n = 4, M = 10, and the operating costs are given by the following table.

 

Then the plan of minimum cost would be the sequence of locations

[NY, NY, SF , SF],

with a total cost of 1+ 3 + 2 + 4 + 10 = 20, where the final term of 10 arises because you change locations once.

(a) Show that the following algorithm does not correctly solve this problem, by giving an instance on which it does not return the correct answer.

For i = 1 to n

If Ni _i then

Output "NY in Month i" Else

Output "SF in Month i"

End

In your example, say what the correct answer is and also what the algorithm above finds.

(b) Give an example of an instance in which every optimal plan must move (i.e., change locations) at least three times.

Provide a brief explanation, saying why your example has this property.

(c) Give an efficient algorithm that takes values for n, M, and sequences of operating costs N₁,..., N_n and S₁,..., S_n, and returns the cost of an optimal plan.