## 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

This entry was posted in Uncategorized. Bookmark the permalink.

### 6 Responses to Homework 6

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

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