Discussion 9
1. We’re asked to help the captain of the USC tennis team to arrange a series of matches against UCLA’s team. Both teams have n players; the tennis rating (a positive number, where a higher number can be interpreted to mean a better player) of the i-th member of USC’s team is ti and the tennis rating for the k-th member of UCLA’s team is bk. We would like to set up a competition in which each person plays one match against a player from the opposite school. Our goal is to make as many matches as possible in which the USC player has a higher tennis rating than his or her opponent. Use network flow to give an algorithm to decide which matches to arrange to achieve this objective.
Solution: Reduce the tournament scheduling problem to Max Flow as follows.
We will construct a flow network G such that G can have a flow of value k iff we can set up k tournament matches such that a USC player has a higher ranking than the UCLA player they play against. The construction will involve the following sets of nodes and edges:
– n nodes representing USC players and n nodes representing UCLA players + a sink node and a source node
– We will connect edges with capacity one from the source to each USC player. We will connect edges from each UCLA player to the sink with capacity one. We will connect an edge from a USC player to a UCLA player if the USC player has a higher ranking than the UCLA player
We will find Max Flow f in G. v(f) will be the number of games in which the USC player has a higher ranking than the UCLA player. The edges carrying flow from a USC player to a UCLA player identify such matches.
If v(f) < n, then the rest of the players can be matched randomly.
Proof: If we were asked to prove that our solution is correct, we would need to show the following:
A – If I find k matches in which USC has an advantage, I can then find a flow of value k in G. B – If we can find a flow of value k in G, we can then find k matches in which USC has an advantage.
To prove A, we can say that if we are given k matches in which USC has an advantage, then we can find k edge disjoint s-t paths (since a given player only participates in one match) in G each one capable of carrying 1 unit of flow. Therefore, we can find a flow of value k in G.
To prove B, we can say that if we have a flow of value k in G, we must have k edges that carrying one unit of flow from a USC player to a UCLA player. Since there is only one unit of flow coming into each node on the USC side and only one unit of flow that can leave a node on the UCLA side, then this edge cannot share any nodes with other edges carrying flow from the USC side to the UCLA side. And since each of these edges identify a pair in which the USC
player has a higher ranking that the UCLA player, we can form k independent matches where USC has an advantage.
2. CSCI 570 is a large class with n TAs. Each week TAs must hold office hours in the TA office room. There is a set of k hour-long time intervals I1, I2, ... Ik in which the office room is available. The room can accommodate up to 3 TAs at any time. Each TA provides a subset of the time intervals he or she can hold office hours with the minimum requirement of lj hours per week, and the maximum mj hours per week. Lastly, the total number of office hours held during the week must be H. Design an algorithm to determine if there is a valid way to schedule the TA's office hours with respect to these constraints.
Solution: Reduce the TA scheduling problem to Circulation with Lower Bounds as follows. We will construct a circulation network G such that G can have a feasible flow iff we can schedule TA office hours with all the given constraints. The construction will involve the following sets of nodes and edges:
- n nodes representing TAs and k nodes representing the hou-long time intervals, a node called s and a node called t
- We will have directed edges from s to each of the n TA nodes, the edge connecting to TA j will have capacity mj and lower bound lj . We will also have edges from each time interval to t with capacity of 3. We will also draw a directed edge from each TA to the set of time intervals in which that TA is available.
- WewillplaceademandvalueofHattandasupplyvalueof-Hats.
We will then solve the feasible circulation problem. If there is a feasible circulation in G, then we can find a feasible assignment of TAs to office hours. Otherwise, there will not be a feasible assignment of TAs to office hours.
3. There are n students in a class. We want to choose a subset of k students as a committee. There has to be m1 number of freshmen, m2 number of sophomores, m3 number of juniors, and m4 number of seniors in the committee. Each student is from one of k departments, where k = m1 +m2 +m3 +m4. Exactly one student from each department has to be chosen for the committee. We are given a list of students, their home departments, and their class (freshman, sophomore, junior, senior). Describe an efficient algorithm based on network flow techniques to select who should be on the committee such that the above constraints are all satisfied.
Solution: Reduce the committee assignment problem to Max Flow as follows.
We will construct a flow network G such that G can have a max flow of value k iff there is a feasible assignment of students to the committee. The construction will involve the following sets of nodes and edges:
- 4 nodes representing freshman, sophomore, junior, and senior classes. n nodes representing students, k nodes representing departments, a node called s and a node called t.
- We will add directed edges from s to the four nodes representing freshman, sophomore, junior, and senior classes with capacities of m1, m2, m3, and m4 respectively. We will connect edges from each node representing a class to all students belonging to that class with capacity of 1. We will add edges from each student to the department they belong to with a capacity of 1. We will add edges from each department to t with a capacity of 1.
We will find max flow f in G. If v(f) = k, then there is a feasible assignment of students to the committee, otherwise there is no such feasible solution.
Note: if If v(f) = k, it means that each edge from a department to t is saturated and also each edge from s to the four classes is saturated (since m1+m2+m3+m4=k). Therefore, the constraints related taking one students from each department and selecting an exact number of freshmen, sophomores, etc. are all met.
4. Given a directed graph G=(V,E) a source node s ε V, a sink node t ε V, and lower bound le for flow on each edge e ε E, find a feasible s-t flow of minimum possible value.
Note: there are no capacity limits for flow on edges in G.
We will solve this problem in two passes. In pass 1 we will find a feasible circulation that meets all lower bound constraints. In the second pass we will take away as much flow from the feasible flow found in the first pass without violating the minimum flow constraints on each edge. Here are the details:
Pass1:AssignacapacityofC=Σ(eεE) le toalledgesinG.Addanedgefromttoswiththe
same capacity and find a feasible circulation f1 in G. Note that C units of capacity will be sufficient to accommodate all minimum flow requirements on all edges, so there will always be a feasible circulation in G. But this feasible circulation may not have the minimum value of flow leaving the source. So in the next pass we will remove the excess flow.
Pass 2: Construct G’ by reversing the edge directions in G (same nodes and edges but edges are in the opposite direction). Then for each edge e we assign it a capacity of f1(e) - le. Note
that this amount (f1(e) - le ) is the excess flow that can be potentially removed from edge e. G’ will have no lower bound constraints on flow and will simply be a flow network.
We then find max flow f2 in G’.
Finally, we will find min flow fmin by subtracting f2 from f1. For example, if the flow f1 over edge e is 10 units and f2 over edge e (but in the opposite direction) is 3 units, then fmin (e) will be 7 units.