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 . It is not just “… every vertex cover “, 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 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).
Advertisements
Leave a Reply