=========================================================================== CSC 373 Homework Assignment 3 Fall 2008 =========================================================================== Due: by 6pm on Tue 25 Nov Worth: 8% For each question, please write up detailed answers carefully: make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks *will* be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions. 1. Give an algorithm that determines whether or not a network N = (V,E) contains a unique cut with minimum capacity. Give a detailed argument that your algorithm is correct, and that it runs in polynomial time. 2. You are consulting for a hospital, to help them schedule doctors. The hospital has a list of the numbers of doctors a_1,a_2,...,a_n that they want to have on hand for the next n days -- they require that *exactly* a_i doctors be scheduled for day i. In addition, each doctor has a list of days A_j when they are available to work. (a) Formulate this problem as a network flow instance. More precisely, describe how to take the numbers a_1,...,a_n and the lists A_1,...,A_k and use network flow techniques to produce a schedule S_1,...,S_k for each doctor such that (1) S_j (_ A_j for each j (i.e., each doctor is scheduled only on days when they are available), (2) there are exactly a_i doctors scheduled on day i, for each i. If there is no such schedule, your algorithm should (correctly) report that fact. Justify that your algorithm runs in polytime and is correct -- explain how flows in your network correspond to schedules, and why your algorithm is guaranteed to produce a correct answer. (b) Let f be a maximum flow in your network from part (a), and X_f be the minimum cut constructed as in the proof of correctness of the Ford-Fulkerson theorem. Answer each question below with respect to cut X_f = (V_s,V_t) and justify each answer carefully -- note that the correct answer may be "it depends"; in particular, there may not be a feasible schedule. i. If doctor j belongs to V_s, can we conclude that S_j = A_j (i.e., that doctor j has been assigned to work on every day when he/she is available)? ii. If doctor j belongs to V_t, can we conclude that S_j = A_j (i.e., that doctor j has been assigned to work on every day when he/she is available)? iii. If day i belongs to V_s, can we conclude that there are exactly a_i doctors assigned to work on day i? iv. If day i belongs to V_t, can we conclude that there are exactly a_i doctors assigned to work on day i? (c) After a few weeks, the hospital finds that doctors tend to submit lists of availability that are too restrictive, and your algorithm almost always reports that there is no possible schedule, which results in much wasted time as doctors must be contacted again to resubmit their availabilities, etc. They decide to take matters into their own hands and introduce a new integer parameter c > 0 to resolve conflicts -- the intention is that doctors can be assigned up to c days outside of their availability list. Give an efficient algorithm that takes the numbers a_1,...,a_n, the lists A_1,...,A_k, and the parameter c > 0, and that produces a schedule S_1,...,S_k for each doctor such that (1) S_j contains at most c days that are not in A_j, for each j, (2) there are exactly a_i doctors scheduled on day i, for each i. As before, if there is no such schedule, your algorithm should (correctly) report that fact. Justify that your algorithm is correct and runs in polytime. 3. A film producer is seeking actors and investors for his new movie. There are n available actors, and actor i charges s_i dollars. For funding, there are m available investors, and investor j will provide p_j dollars, but only on the condition that certain specific actors L_j (_ {1,2,...,n} are included in the cast (*all* of the actors in L_j must be included in order to receive funding from investor j). Give an algorithm to find a set of actors and investors for the movie that maximizes the producer's profits (total funding from the investors minus total cost of actors). Justify that your algorithm is correct. 4. Given a network N = (V,E) where each node v (- V - {s,t} has a "loss coefficient" \epsilon_v (- [0,1] (a real number), we want to compute a maximum flow that satisfies "conservation with loss": for each vertex v (- V - {s,t}, f^out(v) = (1 - \epsilon_v) f^in(v). In addition, the flow must still satisfy the "regular" capacity constraint: f(e) <= c(e) for each edge e (- E. Show how to represent this problem as a linear program (clearly specify your variables, objective function, and constraints). Justify that your LP is correct -- in particular, explain how to reconstruct a solution to the original problem given an optimal solution for your LP. 5. Consider an (n x n) "grid graph", as in the figure below, where each vertex v (- V has a non-negative integer weight w(v) -- for this question, assume that all weights are distinct. v_1 ------ v_2 ------- ... ---- v_n | | | | | | v_{n+1} -- v_{n+2} --- ... ---- v_{2n} | | | : : : | | | v_{n^2-n+1} v_{n^2-n+2} ... ---- v_{n^2} Consider the following "heavy first" greedy algorithm that attempts to find an independent set with maximum total weight in such a weighted grid graph: S = {} while V is not empty: let v_i (- V have maximum weight w(v_i) S = S u {v_i} remove v_i and all v_i's neighbours from V return S Prove that this greedy algorithm has an approximation ratio of 4. (*Hint*: Let S be the IS returned by the greedy algorithm and T be any other IS in G; show that for all v (- T, either v (- S or there is some v' (- S such that (v,v') (- E. What can you say about w(v') and w(v) in that case?)