HW 3

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 p_1, p_2, \ldots, p_n each between 0 and 1 that represents the probability that the “All-Star” team has of beating each of the other n teams in a tournament, i.e. p_i is the probability that All-Star wins against team i.

  • Give an algorithm to compute the probability that this team wins k consecutive games when it plays the n teams in the order 1,2,\ldots, n.
  • Suppose now that after each win the probability of All-Star winning against every other team doubles (if the probability was bigger than 1/2, 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 k games (not necessarily consecutive) when it plays all the other teams in the order 1,2,\ldots, n.

2. Suppose you are given a weighted graph G=(V,E) with weight w : E \rightarrow \mathbb{R}. Let a subset R \subseteq E of the edges be colored red. For every pair of vertices s, t \in V find the minimum weight shortest path between s and t that contains exactly k red edges. (If no such path exists then the weight is supposed to be \infty.)

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 G = (V, E) and weight function w : E \rightarrow \mathbb{R}, define a fractional perfect matching to be a real-valued vector on the edges, x \in \mathbb{R}^E, such that for every vertex v \in V we have \sum_{e: v \in e} x_e = 1 and x_e \ge 0 for every e \in E. The weight of this fractional matching is given by \sum_{e \in E} w_e x_e. Show the following:

  • Given a minimum cost fractional perfect matching x \in \mathbb{R}^E, construct a perfect matching M of weight at most the weight of the fractional matching.
  • Given a maximum cost fractional perfect matching x \in \mathbb{R}^E, construct a perfect matching M of weight at least the weight of the fractional matching.

5. Given a weighted directed graph D = (V, A) and weight function w:A \rightarrow \mathbb{R}, give an algorithm to find a minimum weight cycle cover of D. A cycle cover of a directed graph is a collection of vertex disjoint directed cycles such that every vertex in V 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.

25 Comments

      1. So for 1a, does it mean the first k games it plays (And then they lose all the rest)? or somewhere in the n games, they have a winning streak of exactly k games somewhere in it?

  1. For problem 3, what is meant by “the problem of finding a maximum weight perfect matching”? We’re assuming that we have an algorithm that returns a maximum weight perfect matching, but what does the algorithm return if there is no such perfect matching?

    Reply

  2. Do we consider a single vertex in a directed graph to be a cycle? Because if it is, then problem 5 becomes trivial assuming the weights are nonnegative (simply let the cycle cover be every vertex in the graph. No edges => 0 weight). If we don’t consider it to be a cycle, then not every directed graph has a cycle cover (e.g. the 2-vertex, 1-edge graph “A -> B”). In this case, what should the output of our algorithm be?

    Reply

      1. So I assume that the answer is “no” to my first question, “do we consider a single vertex in a directed graph to be a cycle?”

  3. For the third problem, correct me if I am wrong: you are given the maximum weight perfect matching in G and it is your job to find the maximum weight matching in G

    Reply

    1. I’m not sure, but I think we are given a the maximum edge matching and we need to find the perfect matching with maximum weight if it exists.

      Reply

  4. Just to clarify, for 1a)
    Let’s say the p = [0.5, 0.6, 0.2] (therefore n = 3) and k=2.

    Would the probability of winning 2 consecutive games be 0.3 because:
    P((winning 1 and 2) and losing 3) = 0.5*0.6*0.8
    P((winning 2 and 3) and losing 1) = 0.5*0.6*0.2

    P(winning 2 consecutive games) = (0.5*0.6)(0.2 + 0.8) = 0.3
    Is this correct?

    Reply

  5. For question 2, once you go through an edge as part of a path, can you go back through that path?
    Like in this path, could we go from A to B through the red in the path shown. It goes through the second edge twice.

    Reply

  6. If I understand the definition of fractional matching correctly, isn’t there not necessarily a perfect matching in 4a with weight less than the fractional matching. If there was, why wouldn’t the fractional matching choose weights to effectively make it the perfect matching, thereby getting a lower weight? From my understanding, a perfect matching is basically a fractional matching where x_e can only be 0 or 1.

    Reply

  7. If we decide to use the Hungarian algorithm presented in class, can we just state “use the Hungarian algorithm” or do we have to reprove it?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s