Q1 Teaching Assignment
CSC373 Fall’20 Tutorial 5 Solutions Mon. Oct. 13, 2020
Suppose there are m courses: c1,…,cm. For each j ∈ {1,…,m}, course cj has sj sections. There are n professors: p1,…,pn. For each i ∈ {1,…,n}, professor pi has a teaching load of li, and has a preference for a subset of courses Ai ⊆ {c1, . . . , cm}.
Your goal is to find a feasible assignment of professors to courses such that:
• each professor pi is assigned exactly li courses,
• each course cj assigned to exactly sj professors,
• no professor is assigned a course that they do not prefer, • no professor teaches multiple sections of the same course.
Reduce this problem to the network flow problem. Justify that your reduction is correct. What is the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on the network you created?
Solution to Q1
Create a flow network with the set of vertices {s, t, p1, . . . , pn, c1, . . . , cm} and the following edges: • (s,pi) with capacity li, for each pi;
• (cj,t) with capacity sj, for each cj;
• (pi,cj) with capacity 1, for each pi and cj such that pi prefers to teach cj (i.e. cj ∈ Ai).
The reduction now proceeds as follows.
1. Compute a maximum flow f in this network via the Ford-Fulkerson algorithm. Note that it will return an integral flow.
2. If f(s,pi) = li for each professor pi and f(cj,t) = lj for each course cj, then a feasible assignment exists. Assign pi to teach cj whenever f(pi,cj) = 1.
3. Otherwise, a feasible assignment does not exist.
To see that this algorithm is correct, we notice that there is a 1-1 correspondence between an
integral flow f and an assignment of professors to courses in the following way: • f(pi,cj) = 1 if and only if pi is assigned to teach cj, and 0 otherwise.
• f(s,pi) is the number of courses that pi is assigned to teach.
• f(cj,t) is the number of professors assigned to course cj.
1
Due to the way the edges are created in the flow network, the third and fourth constraints in the problem statement are satisfied in the assignment corresponding to any valid flow. Therefore, a feasible assignment exists if and only if the maximum flow f satisfies f(s,pi) = li for each professor pi and f (cj , t) = sj for each course cj , as we are checking in the second step.1
This flow network has m+n+2 vertices and m+n+ni=1 |Ai| ≤ m+n+m·n edges. The sum of capacities of edges leaving s is ni=1 li ≤ ni=1 m = n · m.2 Hence, the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm is O(n2 · m2), which is polynomial in the input length.
Q2 Mobile Computing
Suppose there are n mobile computing clients in a certain town. Each client i ∈ {1, . . . , n} is located at a given point (xci,yic), and must be connected to exactly one of m “base stations”. We are also given the coordinates (xbj,yjb) of each base station j ∈ {1,…,m}.
There is a “range parameter” r: a client can only be connected to a base station within a Euclidean distance of r. There is also a “load parameter” L: no more than L clients can be connected to any single base station.
Reduce this problem to the network flow problem. Justify that your reduction is correct. What is the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on the network you created?
Solution to Q2
Create a flow network with the set of vertices {s, t, c1, . . . , cn, b1, . . . , bm} (where ci represents client i and bj represents base station j) and the following edges:
• (s,ci) with capacity 1, for each ci; • (bj,t) with capacity L, for each bj;
• (ci,bj)withcapacity1,forallci andbj suchthat(xci −xbj)2+(yic−yjb)2 ≤r.3 The reduction now proceeds as follows.
1. Compute a maximum flow f in this network via the Ford-Fulkerson algorithm. Note that it will return an integral flow.
2. If f(s,ci) = 1 for each client i, then a valid assignment exists. In this case, for each client i, because ci is receiving a unit flow from s and f is integral, there will be a unique j such that f(ci,bj) = 1. Assign each client i to base station j such that f(ci,bj) = 1.
3. Otherwise, a valid assignment does not exist.
1 Note that the capacity constraints would only ensure f (s, pi ) ≤ li and f (cj , t) ≤ sj ; they would not ensure equality.
2Clearly, for a feasible solution to exist, we must have li ≤ m for each i. If you prefer, you can add a preprocessing step where you check this and return “No feasible solution exists” if it is violated.
3Putting any capacity on this edge that is at least 1 will yield the same maximum flow because, due to (s,ci) having capacity 1, only a unit flow can enter ci, so only a unit flow can leave ci.
2
The proof of correctness is similar to that in Q1. The 1-1 correspondence between an integral flow f and an assignment of clients to base stations is given as: f(ci,bj) = 1 if and only if client i is assigned to base station j. The way the edges are created ensures that the range constraints are respected. The capacity of L on each (bj,t) edge ensures that the load constraints are also respected. Thus, a valid assignment exists if and only if each client is actually assigned, i.e., if each ci receives a flow of 1 from s, as we check in the second step.
The flow network has m+n+2 vertices and at most m+n+m·n edges. The total capacity of edges leaving s is n. Hence, the worst-case running time of the na ̈ıve Ford-Fulkerson is O(m · n2).
3