College of Computer & Information Science Spring 2004 Northeastern University Handout 7 CSG399: Approximation Algorithms 10 March 2003

Problem Set 4

All of the exercises in this problem set concern linear programming, duality, and its application to approximation algorithms. Some of these problems will be discussed at one of our discussion sessions, while others I would like you to turn in your written solutions. Hand-written answers would suffice. Discussion session on March 15

1. Exercise 12.7.

2. Exercise 12.10. Due on March 24

3. Exercise 12.1.

4. Exercise 12.11.

5. Exercise 13.1. Discussion session on March 29

6. Part 3 of Exercise 13.4.

7. Exercise 13.7.

8. Exercise 15.6.