Homework 2 is graded. (Sorry for the delay, it’s my fault — AG). The average was (20/25). Some comments:
1. Most people got this, although in some cases with pretty long-winded proofs. The brief point is that when considering non-integral edges, every vertex on the V side has degree 0 or at least 2; thus one can find either a cycle (as in class) or else the maximal path starts and ends with a degree-1 vertex in U. Deepak cleverly pointed out that you can also just add |U|-|V| fictitious jobs called “unemployment”, link everyone to them with weight 0, and then reduce to the proof from class.
2. George & Leslie = Nemhauser & Trotter. Most people got this too, except in part (b) very few people observed out that for $x$ non-half-integral, $x^+$ and $x^-$ are distinct from $x$. Since this was really the only point to the question we should have deducted a point for failing to mention it. But we did not have the heart to do so.
3. Most people got the first 4 parts, and also the “easy” direction of Farkas Lemma (that both alternatives cannot be true). Some people had trouble with the last part (proving that if there is no feasible x then there must be a y): in particular, I saw proofs that tried to do it from first principles, where the hope was that you’d just use the template from the above parts (and use the correctness of the Avis-Kaluzny procedure).
4. This one tripped almost everyone up: very few of you even mentioned that one might not be able to reach the actual optimal LP value using binary search, and that some kind of “rounding” step would be needed at the end when the size of the binary search intervals is small enough. (That would have sufficed, since we didn’t really expect you to do this rounding step.) The details are all in the sample solutions: even if you don’t read all the solutions, have a look at this one for sure!
5. (Note: for this problem we should have stated that clauses always contain distinct literals. But this didn’t seem to trip anyone up.) Most everyone got (a) and (b). To some extent the point of this question was that for (c), the analysis is much easier than the proof that Horn-Sat is in P. All you have to do is say, “Given a solution with LP-value m, round each value down.” It’s very quick to check that the resulting integer solution still has value m.
Leave a Reply