Textbook Exercise 29 in Chapter 7. Show how to solve this problem by reformulating it to the problem of finding a minimum cut from a flow network built from the set V of n applications v1, v2, ..., and vn in a manner similar to the approach used in the image segmentation problem (see Section 7.10). State clearly what the source node s and the sink node t each represent and how to represent in the flow network the n applications, the benefit bi of porting an application vi to the new system, and the expense (or penalty) xij of two applications vi and vj being separated.

29. Some of your friends have recently graduated and started a small com Santa which they are currently running out of their parents' garages in old Clara They're in the process of porting all their software from system to a new, revved-up system and they're facing the following problem They have a collection of n software applications, t1, 2,...,n), run- ning on their old system and they'd like to some of these to the new stem. If they move application i to the new system, they expect a net (monetary) benefit of bi 20. The different software applications interact with one another, if applications i and j have extensive interaction, then the company will incur an expense if they move one of i or j to the new system but not both; let's denote this expense by xu 20. So, if the situation were really this simple, your friends would just port all n applications, achieving a total benefit of bi. Unfortunately there's a problem. Due to small but fundamental incompatibilities between the two systems, there's no way to port application 1 to the new system; it will have to remain on the old system. Nevertheless, it might still pay off to port some of the other applications, accruing the associated benefit and incurring the expense of theinteractionbetween applications on different Systems So this is the question they pose to you: Which of the remaining applications, if any, should be moved? Give a polynomial-time algorithm to find a set s s (2, 3 nh for which the sum of the benefits minus the expenses of moving the applications in s to the new system is maximized