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, along with basic combinatorial optimization problems.
Grading: determined by homework assignments (submissions in singles not pairs). There is no final exam.
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, along with basic combinatorial optimization problems.
Grading: determined by homework assignments (submissions in singles not pairs). There is no final exam.