Approximation Algorithms
5
Algorithms and machine learning
Advanced studies
Design techniques of approximation algorithms: greedy algorithms and local search, rounding data and dynamic programming, linear programming relaxations. Example problems: Vertex Cover, Set Cover, Metric Steiner Tree and TSP, Knapsack, Bin Packing. (A larger course with the same name was given in 2010.) Prerequisites: the course Design and Analysis of Algorithms or equivalent. Course book: D. P. Williamson, D. B. Shmoys: The design of Approximation Algorithms, Cambridge University Press, 2011.
Lectures
| Time | Room | Lecturer | Date |
|---|---|---|---|
| Tue 12-14 | C222 | Juha Kärkkäinen | 15.01.2008-21.02.2008 |
| Thu 10-12 | C222 | Juha Kärkkäinen | 15.01.2008-21.02.2008 |
| Tue 12-14 | C222 | Juha Kärkkäinen | 11.03.2008-24.04.2008 |
| Thu 10-12 | C222 | Juha Kärkkäinen | 11.03.2008-24.04.2008 |
Exercise groups
| Time | Room | Instructor | Date | Observe |
|---|---|---|---|---|
| Tue 10-12 | C221 | Pasi Rastas | 21.01.2008—22.02.2008 | |
| Tue 10-12 | C221 | Pasi Rastas | 10.03.2008—25.04.2008 |