December 4, 2011

## Homework 6 bug fixes

Check out the comments in this post for fixes. In short, they involve question 1 (the $A$ should be $D$), and question 5b (the expression should be $3/2 OPT + 1/2 c(s,t)$).

November 26, 2011

## Homework 6 posted

For those of you who weren’t in class on Tuesday: Homework #6 is on the webpage. The number of problems you must solve is based on the number of times you scribe for the course.

November 9, 2011

## Homework 5 Due Date

is Tuesday Nov 15th. (Not Thursday Nov 15th, as listed earlier.)

November 2, 2011

## Homework 5 posted

Homework 5 has been released. It’s due Nov 15th.

November 1, 2011

Homework 3 has been graded. The average was 16. Some comments (the detailed solutions are on the webpage, with the solution to problem 1 to be posted tomorrow).

1. Most of you got this one right. The reason why the binary search solution was not strongly poly-time was that the number of steps depends on the size of the numbers involved.

2. For this one, a few solutions tried proving it from first principles. All these statements can be proved in that way, but the easier way is to prove one version of the Farkas lemma (which you’ve already done in HW2) and then reduce these other versions to that one.

3. No surprises here, nothing to report.

4. Perhaps a majority of the solutions reduced it to standard matching and used Hall/Konig’s theorem to prove this statement. Perfectly kosher, even though I was hoping for the duality-based solution.

We give back the graded HWs 2 and 3 at the end of lecture tomorrow.

October 26, 2011

## Homework Sample Solutions

In case you hadn’t noticed, we’ve been trying to put up sample solutions for the HWs: complete solutions for HW2, and partial solutions for HW3 are now online (I still need to write the solutions for HW3 #1).

October 26, 2011

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.

October 19, 2011

There’ve been some corrections to homework 4, just in case you missed those.

Also, for the matroid problem (#2): if you’ve not seen matroids before, you might find it useful to think about the arguments in the special case of the graphical matroid first. In a graphical matroid, the elements are edges of some graph G, and the independent sets are all forests (acyclic subgraphs) of this graph.

October 11, 2011

## Homework 4

Homework 4 is posted.  It is due Thursday Oct. 20.

Update: In problem 2, the universe for the matroid is a finite set. (thanks Tim!)

Update #2: In problem 2, the red and blue rules have been corrected (you only want to pick cuts with no blue edges, or cycles with no red edges) in the latest version online. (thanks Brian!)

Update #3: In problem 6a, should read $B(0,1/R) \subseteq K^* \subseteq B(0,1/r)$ and not $\ldots \subseteq K \subseteq \ldots$.

October 10, 2011

## Homework 3 clarifications

Two typos for HW3, and also a couple of clarifications. First, the typos:

• In Problem #4 (the min-max theorem for b-matchings), the last sentence should read “… for every vertex cover $C \subseteq U \cup V$. It is not just “… every vertex cover $C \subseteq V$“, which is clearly false.
• In Problem #3c, it should read “infer that the coefficients of the non-basic variables in the last line of the tableau are…”

And for the clarifications:

• In the certifying LP solver, (Problem #2a) for the unbounded case, you should ideally show not only how to find the $x,r$ satisfying those properties, but also prove why such a pair of vectors must exist.
• And finally, whenever we want you to take an LP and write a new LP (as in Problem #2c), you should take care that if the original LP had size S (according to the definition of size from Hwk1), the new LP should have size only poly(S).