601.433/633 Introduction to Algorithms Fall 2019
Homework #7 Due: November 21, 2019, 12pm
Remember: you may work in groups of up to three people, but must write up your solution entirely on your own. Collaboration is limited to discussing the problems – you may not look at, compare, reuse, etc. any text from anyone else in the class. Please include your list of collaborators on the first page of your submission. You may use the internet to look up formulas, definitions, etc., but may not simply look up the answers online.
Please include proofs with all of your answers, unless stated otherwise.
1 Graduation Requirements (66 points)
John Hopskins University1 has n courses. In order to graduate, a student must satisfy several requirements of the form “you must take at least k courses from subset S”. However, any given course cannot be used towards satisfying multiple requirements. For example, if one requirement says that you must take at least two courses from {A,B,C}, and a second requirement states that you must take at least two courses from {C,D,E}, then a student who has taken just {B,C,D} would not yet be able to graduate as C can only be used towards one of the requirements.
Your job is to give an efficient algorithm for the following problem: given a list of requirements r1, r2, . . . , rm (where each requirement ri is of the form “you must take at least ki courses from set Si”), and given a list L of courses taken by some student, determine if that student can graduate.
(a) (22 points) Given the m requirements and list of L courses taken (as above), design a flow network so that the maximum flow is mi=1 ki if and only if the student can graduate.
(b) (22 points) Using the previous part, design an algorithm for the problem which runs in O(|L|2m) time. Prove correctness and running time.
Now suppose that John Hopskins University changes their graduation requirements. Every time a student takes a class, they get some grade in [0, 1]. They must satisfy several requirements of the form “the sum of your grades in courses taken from set S must be at least ki”. The goal of this problem is to take on the role of the student, and figure out the least possible work they can do while still passing.
More formally, there is a set of n classes. Without loss of generality, we will simply say that this is the set [n] = {1,2,…,n}. We are also given m subsets S1,S2,…,Sm where each Sj ⊆ [n], and m values k1,k2,…,km ∈ R. If a student puts in xi ∈ [0,1] amount of work into class i, we assume that they will get xi as a grade (i.e., the grade they receive is exactly equal to the amount of work they put into it). In order to graduate, for every j ∈ [m], the sum of the grades they receive in the classes in Sj must be at least kj (not taking a class is equivalent to putting in no work, and hence getting a grade of 0). Our goal is to minimize the total amount of work the student has to do while still graduating.
Note that unlike the previous requirements, now if some class i appears in both Sj and Sj′, then it will count towards both requirement j and requirement j′.
1 https://www.youtube.com/watch?v=JEH2ha1p0WA
1
(c) (22 points) Show how this problem can be solved in polynomial time by using linear pro- gramming. Be sure to specify what the variables are, what the constraints are, and what the objective function is.
2 More Flows (34 points)
In class we (briefly) saw the Multicommodity Flow problem: given a directed graph G = (V,E), capacities c : E → R+, and a collection of k source-sink pairs {(si, ti)}i∈[k], maximize the total flow sent (summed over all of the k commodities). In this setting each commodity i must itself be a valid si −ti flow (satisfying flow-balance constraints), while together (summed over all commodities) they must satisfy all edge capacity constraints. We saw how to write a linear program for this problem.
Let’s consider a different variant: the Scaled Multicommodity Flow problem. We are again given a directed graph G = (V,E), capacities c : E → R+, and a collection of k source-sink pairs {(si,ti)}i∈[k], but we are also given demands d : [k] → R+ for each commodity. Think of d(i) as the amount of commodity i that we want to send from si to ti. Of course, it might not be possible to satisfy all of this demand. In that case, we could just send as much as we can, which gets us back the Multicommodity Flow problem. But that might be very unfair to some commodities, who might (for example) get 0 flow while other commodities get their entire demand. To fix this, we will instead try to scale all demands down proportionally until we can actually satisfy this scaled demand.
Slightly more formally, in the Scaled Multicommodity Flow problem our objective is to find the largest value λ such that the it is possible to simultaneously send λ · d(i) flow from si to ti for each commodity i ∈ [k] subject to each commodity obeying the flow-balance constraints, and the total flow (summed over all commodities) satisfying the edge capacity constraints.
Show how to use linear programming to solve the scaled multicommodity flow problem. Be sure to specify what the variables are, what the constraints are, and what the objective function is.
2