582456 Approximation Algorithms (8 cr, 4 cu), spring 2008, periods III and IV

The course provides an introduction is to approximation algorithms for NP-hard optimization problems.

Prerequisites

Design of Algorithms (Algoritmien suunnittelu), Complexity of Computation (Laskennan vaativuus)

Lectures

Juha Kärkkäinen | 15.01.-21.02. and 11.03.-24.04. | Tue 12-14, Thu 10-12 C222

Exercise sessions

Pasi Rastas | 22.01.-19.02. and 11.03.-22.04. | Tue 10-12 C221

• Assignments are on the course Wiki pages.

Exams

Mon 25.02. 9-12 and Mon 28.04. 9-12.

Lecture notes

Lecture material will be collected to the course Wiki pages.

• Each student must write the lecture notes of one lecture to the Wiki.

Grading

60 points

• exams: 20+20
• exercises: 10
• small project: 10

Literature

1. Vijay V. Vazirani, Approximation Algorithms, Springer, 2002

Links

• A compendium of NP optimization problems

---

Juha Kärkkäinen