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