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

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)?

Like

• Indeed, you can assume that $\alpha = O(\log n \log\log n)$, since there exists a probabilistic embedding into trees with that guarantee.

Like

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.

Like

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

Like

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.

Like

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

Like