Due date: Friday, March 6, at the start of class.
Submissions: Please submit your printed or hand written solutions in class. If you have a compelling reason for not being able to attend that particular class, please email your submissions to the instructor or the TA.
Policy: Write your own solutions independently; include the names of anyone you discussed the problems with.
1. Suppose we are given a list of numbers each between and that represents the probability that the “All-Star” team has of beating each of the other teams in a tournament, i.e. is the probability that All-Star wins against team .
- Give an algorithm to compute the probability that this team wins consecutive games when it plays the teams in the order .
- Suppose now that after each win the probability of All-Star winning against every other team doubles (if the probability was bigger than , then the probability becomes 1) and after every loss the probability of All-Star winning against every other team halves. Give an algorithm to compute the probability that All-Star wins games (not necessarily consecutive) when it plays all the other teams in the order .
2. Suppose you are given a weighted graph with weight . Let a subset of the edges be colored red. For every pair of vertices find the minimum weight shortest path between and that contains exactly red edges. (If no such path exists then the weight is supposed to be .)
3. Give a polynomial time reduction from the maximum matching problem to the problem of finding a maximum weight perfect matching.
4. Given a weighted bipartite graph and weight function , define a fractional perfect matching to be a real-valued vector on the edges, , such that for every vertex we have and for every . The weight of this fractional matching is given by . Show the following:
- Given a minimum cost fractional perfect matching , construct a perfect matching of weight at most the weight of the fractional matching.
- Given a maximum cost fractional perfect matching , construct a perfect matching of weight at least the weight of the fractional matching.
5. Given a weighted directed graph and weight function , give an algorithm to find a minimum weight cycle cover of . A cycle cover of a directed graph is a collection of vertex disjoint directed cycles such that every vertex in is in one of the cycles.
6. (Bonus) In the Hungarian algorithm for bipartite matching, suppose, in each phase, you augment on a maximal set of disjoint shortest augmenting paths. Show that the the length of the shortest augmenting path increases in each phase.