University of Southern California CSCI 570 DIS-09 with solutions-VERIFIED BY EXPERTS

Document Content and Description Below

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 c... an 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 [Show More]

Last updated: 1 year ago

Preview 1 out of 3 pages