(Solved): Given is a line graph with costs on vertices and distances on edges. You can think of vertices as ci ...

Given is a line graph with costs on vertices and distances on edges. You can think of vertices as cities on a particular highway. And we want to select few of these cities where to open a chain of restaurants. Each city has a particular cost of real-estate and each city also has a particular statistical demand. For the city where there is no restaurant, they will go to the closest restaurant. But this comes at a travel cost. Overall, modelled as a graph problem (or a line problem) cost of opening facility at vertex i is given by wi. The cost of travel for each vertex v is the distance between v to its closest vertex having a facility. We want to minimize the sum of facility costs plus travel costs. (for simplicity we’ll assume each city has unit demand). For example, consider the following graph. If we open facilities at 2nd, 4th and 7th locations, the total facility cost is 8 + 10 + 5 = 23 but total travel cost is 5+0+1+0+1+6+0+10 = 23 which makes total cost of 46. However, if we choose to open facilities at 1st, 5th and 8th locations then total facility cost is 5 + 7 + 4 = 16 and the travel costs would be 0+5+2+1+0+5+10+0 = 23 which makes the total cost of 39. We need to find an algorithm to find the minimum such cost. The algorithm will output the subset of vertices where the facilities should be opened. Give a dynamic programming algorithm for this purpose, what is the best time complexity you can think of for executing this.