Homework 3 released

Hi all: HW3 is out, due next Friday. 4 problems, related to low-stretch spanning trees and matchings.

Ask questions/clarifications here, and I will also post corrections below.

Edit: see comments for corrections. Also, fixed the online PDF file with changes.

This entry was posted in Uncategorized. Bookmark the permalink.

7 Responses to Homework 3 released

  1. Adam says:

    I’m confused on 1.b.ii.
    Is alpha just given to us as an input to the problem? Do we know how alpha relates to n? Like is it O(1), O(n) etc? Or can assume alpha is O(log n log log n)?


  2. Adam says:

    Okay thanks. Another couple of questions about question 3:

    It says the naive algorithm runs in O(nW)*T(n)…but this doesn’t seem to make sense in light of the fact that some edge weights are negative. Obviously this fails if W is negative. But it seems like it would also fail if W were slightly positive but all of the other edge weights were negative. It seems like we really want W=maxEdge-minEdge or something like that.

    Also if I’m not mistaken the formula in part (c) doesn’t work when the current matching is the min-weight perfect matching, because in this case you aren’t guaranteed that a cycle exists at all. Imagine the case where every point is only adjacent to a single edge.

    Could you please clarify?


    • Indeed, Adam, you’re correct: define W = \max_e |w_e| the maximum absolute value, that will fix it. And for (c) read it as saying: if M is not a min-weight perfect matching then there exists a cycle with that weight ratio.


  3. Adam says:

    Thank you!
    If I may ask another question…on problem 3.d, is T(n) the time to find a negative cycle, or is it the time to find the most negative cycle? Naively, finding the most negative cycle seems significantly more difficult than the rest of the problem.


    • Oops, T(n) in that part is supposed to be the time to find a minimum weight-ratio cycle in a graph. It is slightly more than the time to find a negative cycle in the graph. (From HW2, problem 1)

      Finding the most negative cycle in a graph (which is different from finding the minimum weight-ratio cycle) is NP-hard, since the Hamilton cycle problem reduces to it (just take a graph and put weight -1 on all edges, the graph has a cycle of length -n if and only if it has a Hamilton cycle).


  4. Adam says:

    Oh I read that part wrong. Thank you!


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