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.
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.
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.
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.