MAT-72606 Approximation Algorithms, 4 cr

Prof. Tapio Elomaa

Spring 2015, period IV

Lectures: Mar. 17 - May 12
Weekly exercises: M.Sc. Juho Lauri, Mon 10 - 12 TC315
Course exam: Mon. May 25, 2015

- Lectures

The course is based on the textbook:

WeekDatesSlidesExercises Chapters in the Book
1 Mar. 17 & 19 1 - 49 n/a 1 Introduction
2 Mar. 24 & 26 50 - 95 Mar. 23 1, 2 Greedy algorithms and local search
3 Mar. 31 & Apr. 9 96 - 137 Mar. 30 2, 3 Rounding data and dynamic programming
4 Apr. 14 & 16 138 - 171 Apr. 13 3
5 Apr. 21 & 23 172 - 206 Apr. 20 4 Deterministic rounding of linear programs
6 Apr. 28 & 30 207 - 240 Apr. 27 5 Random sampling and randomized rounding of LPs
7 May 5 & 7 241 - 281 May 4 6 Randomized rounding of semidefinite programs
8 May 12 May 11 RECAP

- Contents

  1. Introduction
  2. Greedy algorithms and local search
  3. Rounding data and dynamic programming
  4. Deterministic rounding of linear programs
  5. Random sampling and randomized rounding of linear programs
  6. Randomized rounding of semidefinite programs
  7. The primal-dual method
  8. Cuts and metrics


Jun. 25, 2015 http://www.cs.tut.fi/~elomaa/