Algorithmic consulting Professor Gore wants to open up an

Chapter 26, Problem 26-3

(choose chapter or problem)

Algorithmic consulting Professor Gore wants to open up an algorithmic consulting company. He has identified n important subareas of algorithms (roughly corresponding to different portions of this textbook), which he represents by the set A D fA1; A2;:::;Ang. In each subarea Ak, he can hire an expert in that area for ck dollars. The consulting company has lined up a set J D fJ1; J2;:::;Jmg of potential jobs. In order to perform job Ji, the company needs to have hired experts in a subset Ri A of subareas. Each expert can work on multiple jobs simultaneously. If the company chooses to accept job Ji , it must have hired experts in all subareas in Ri , and it will take in revenue of pi dollars. Professor Gores job is to determine which subareas to hire experts in and which jobs to accept in order to maximize the net revenue, which is the total income from jobs accepted minus the total cost of employing the experts. Consider the following flow network G. It contains a source vertex s, vertices A1; A2;:::;An, vertices J1; J2;:::;Jm, and a sink vertex t. For k D 1; 2 : : : ; n, the flow network contains an edge .s; Ak/ with capacity c.s; Ak/ D ck, and for i D 1; 2; : : : ; m, the flow network contains an edge .Ji;t/ with capacity c.Ji;t/ D pi. For k D 1; 2; : : : ; n and i D 1; 2; : : : ; m, if Ak 2 Ri, then G contains an edge .Ak; Ji/ with capacity c.Ak; Ji/ D 1. a. Show that if Ji 2 T for a finite-capacity cut .S; T / of G, then Ak 2 T for each Ak 2 Ri. b. Show how to determine the maximum net revenue from the capacity of a minimum cut of G and the given pi values. c. Give an efficient algorithm to determine which jobs to accept and which experts to hire. Analyze the running time of your algorithm in terms of m, n, and r D Pm iD1 jRij.