Homework 6

Hi all: the final HW has been posted. It’s a little longer with 6 questions (the first three are questions you must solve individually, the last three allow collaboration). The due date is April 17th, but see if you can get it done early before the busy days towards the end of the semester.

Questions, as always, in the comments. (For the individual questions, if you think your question might be too leading for others, just send mail.)

Also, do have a look at the first exercise before next Friday, it will help you become more familiar with positive semi-definite (psd) matrices, which we will be using quite a bit for the next lecture…

–Anupam

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Homework 6

  1. Adam says:

    Forgive me if this is obvious, but where is H_k from problem 1.a. actually defined? I see it in the notes but I don’t see a definition. (This was the only lecture I missed all semester; I had a recitation for another class 😦 )

    Like

  2. Adam says:

    I’m a little confused on 3.c.
    It says “show that there exists an optimal (integer) solution such that C is a subset of V_{1/2} U V_{1}”
    It sounds like it’s simultaneously asking for an integer solution while also saying that half-integral values are allowed…is it possible to clarify without giving too many details away? Thanks!

    Like

    • AnupamG says:

      Think of it this way: you can solve the LP (in poly-time), and it gives you a “half-integral” solution. (Some variables are equal to 1, and some are equal to 1/2.) Of course, this is just the optimal LP solution. These values may or may not have anything to do with the optimal vertex covers (which are NP-hard to compute).

      What the problem says is: prove that there actually *exists* an integer solution which is contained within the vertices to which the LP gives non-zero values.

      Like

  3. Adam says:

    For problem 4.c., do we need to prove var(Xtilde, Ytilde)< 1/d X_F^2 Y_F^2? Or is that given to us?

    Like

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s