Approximation Algorithms


Approximation Algorithms



Thomas Rothvoß


A large fraction of interesting dicrete optimization problems are NP-hard, that means there is no hope in finding exact, optimum solutions efficiently – all known algorithms for this goal have exponential running time. Hence a growing field in theoretical computer science and discrete mathematics deals with approximation algorithms. These algorithms need only polynomial time and obtain solutions whose values are within a provably small ratio from the optimum. We will present fundamental approximation algorithms for example for

  • Steiner tree
  • k-Center
  • TSP
  • Set Cover
  • Knapsack
  • Multi Constraint Knapsack
  • Bin Packing (including the AFPTAS by Karmarkar & Karp)
  • Scheduling on unrelated parallel machines
  • Scheduling on parallel identical machines
  • Facility Location
  • Tree embeddings
  • MaxCut (via semidefinite programming)
  • Max-2-Sat (via semidefinite programming)

The lectures and the exercises will be given in English. The only prerequisit is a basic knowledge of algorithms. Please note that this is a theory course, hence there will be no kind of implementation/coding. This is a 4-credit doctoral course. The ID is MATH-724.


Lectures: Wednesday, 14:15-15:45, ELD 120 (starting from 24.02.10)

Exercises: Wednesday, 16:00-17:30, ELD 120 (starting from 03.03.10)

On May 5, lecture and exercise are moved to room AAC 132 (due to the Balelec festival).


Slides of Lecture (last update: June 2) 


Exercise sheet 1 Solution 1  

Exercise sheet 2 Solution 2  

Exercise sheet 3 Solution 3  

Exercise sheet 4 Solution 4  

Exercise sheet 5 Solution 5  

Exercise sheet 6 Solution 6  

Exercise sheet 7 Solution 7  

Exercise sheet 8 Solution 8  

Exercise sheet 9 Solution 9  

Exercise sheet 10 (updated on May 11) Solution 10  

Exercise sheet 11 Solution 11  

Exercise sheet 12  


There will be an oral exam at the end of the semester. This is a 4-credit course. Here is a link to the course book webpage page.