Credit points: 2.0
An approach for coping with the apparent intractability of many NP-hard problems is to look for the best approximate solution, while maintaining polynomial running time. In this course, the basic notions of approximation algorithms, such as a fully polynomial approximation scheme, are reviewed. A wide variety of techniques for approximating problems in combinatorial optimization are discussed.
This is a graduate level course on the design and analysis of combinatorial approximation algorithms for NP-hard optimization problems. The course is tailored for students with a strong inclination towards theory. However, students interested in networks, computer vision, computational biology, and other areas could benefit from this course
Prerequisites: Students are expected to possess elementary knowledge in graph theory, computational complexity, linear programming, and the probabilistic method. A few good sources for such knowledge are listed under “liteature -> references”. We will need just a tiny portion of their content.
Grading policy: The final grade will be based on grading homework assignments.
(*) Meets on: 2008/9 Winter Semester, Thursdays 10:30 - 12:30, Taub 5.