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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: