MAT-72606 Approximation Algorithms, 4 cr

Prof. Tapio Elomaa

Spring 2017, period IV

Lectures: Mar. 6 - Apr. 26

- Lectures

The course is based on the textbook:

- 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


Oct. 13, 2016 http://www.cs.tut.fi/~elomaa/