Homework Assignment 3

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 a1,a2,...,an that they want to have on hand for the next n days — they require that exactly ai doctors be scheduled for day i. In addition, each doctor has a list of days Aj when they are available to work.

    1. Formulate this problem as a network flow instance. More precisely, describe how to take the numbers a1,...,an and the lists A1,...,Ak and use network flow techniques to produce a schedule S1,...,Sk for each doctor such that

      1. Sj ⊆ Aj for each j (i.e., each doctor is scheduled only on days when they are available),
      2. there are exactly ai 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.

    2. Let f be a maximum flow in your network from part (a), and Xf be the minimum cut constructed as in the proof of correctness of the Ford-Fulkerson theorem. Answer each question below with respect to cut Xf = (Vs,Vt) and justify each answer carefully — note that the correct answer may be "it depends"; in particular, there may not be a feasible schedule.

      1. If doctor j belongs to Vs, can we conclude that Sj = Aj (i.e., that doctor j has been assigned to work on every day when he/she is available)?

      2. If doctor j belongs to Vt, can we conclude that Sj = Aj (i.e., that doctor j has been assigned to work on every day when he/she is available)?

      3. If day i belongs to Vs, can we conclude that there are exactly ai doctors assigned to work on day i?

      4. If day i belongs to Vt, can we conclude that there are exactly ai doctors assigned to work on day i?

    3. 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 a1,...,an, the lists A1,...,Ak, and the parameter c > 0, and that produces a schedule S1,...,Sk for each doctor such that

      1. Sj contains at most c days that are not in Aj, for each ,
      2. there are exactly ai 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 si dollars. For funding, there are m available investors, and investor j will provide pj dollars, but only on the condition that certain specific actors Lj ⊆ {1,2,...,n} are included in the cast (all of the actors in Lj 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" ε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}, fout(v) = (1 - εv) fin(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 × 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. 

          v1 ------ v2 ------ ... --- vn
       |        |                  |
       |        |                  |
      vn+1 ---- vn+2 ---- ... ---- v2n
       |        |                  |
       :        :                  :
       |        |                  |
      vn2-n+1 - vn2-n+2 -- ... ---- vn^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 vi ∈ V have maximum weight w(vi)
    S = S ∪ {vi}
    remove vi and all vi'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?)