L25 Slides

We finished our discussion of linear programming and introduced the idea of reductions between problems. This lecture, we reviewed what is expected for the reductions that you need to create to solve the homework problems. We then introduced the independent set problem and the vertex cover problem; in the next lecture we will show these problems to be equivalent.