Wednesday, February 6, 2008

Solution to 7a on Homework 1

Here is a solution to problem 7a on homework 1. To get the full $1 - 1/(k-1) - \delta$ vs. $\epsilon$ hardness result for Max-Ek-Independent-Set (a problem we will discuss in tomorrow's class), you need to use something similar, and that something similar might be on the next homework...

No comments: