Suppose youre running a lightweight consulting businessjust

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. youll incur an operating cost of N_I ff you run the business out of NY; youll 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 t. 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 problen. Given a value for the moving cost M, and sequences of operating costs N_1, .... N_n and S_1, ..., 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, SR SF} with a total cost of 1 + 3 + 2 + 4 + 10 = 20, where the final term of 10 arises because you change locations once. 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 = I to n If Ni

Solution

Part A:

The algorithm does not consider the cost for moving. It only considers the minimum cost of operation between two cities. Consider the case when moving cost is greater than the operations cost saved by changing city.

e.g.:
3 months
NY: 4 2 3
SF: 3 3 2
Moving cost 5. The alogirthm will choose SF,NY,SF. But the total cost will be 3+5+2+5+2 which is 17. The optimal solution is to just stay in SF for all 3 months. The cost will be only 8.

Part B:

e.g.:
4 months
NY: 4 2 3 2
SF: 3 3 2 3
Moving cost 0. Here moving cost is zero. The algorithm proposed in part A will work perfectly. So we have to every month, which is 3 times.

Part C:

f(k+1,NY) = min(f(k,SF)+M,f(k,NY))+ (NY for month k+1)

f(k+1,SF) = min(f(k,NY)+M,f(k,SF))+ (SF for month k+1)

If there n months the output is min(f(n,SF),f(n,NY))

Part D:
Let NY and SF be arrays of length n, which represent operational costs in n months.

M be the moving cost.

We construct an array C[n][2].

C[1][1] = NY[1]
C[1][2] = SF[1]

for i = 2:n
C[i][1] = min(C[i-1][2]+M,C[i-1][1])+NY[i]
C[i][2] = min(C[i-1][1]+M,C[i-1][2])+SF[i]

answer = min(C[n][1],C[n][2])