Many optimization problems frequently occuring in practise are NP-hard. If P and NP are not the same, then this means that solving these important problem may not be feasible as they require to many resources (time and memory).

One possible approach is to give up on finding an exact solution to the given optimization problem but instead settle for an approximate solution instead. This gives rise to the area of approximation algorithms for NP-hard optimization problems.

In the course of this seminar there will first be an introduction into the area of approximation algorithms and its complexity classes. Then there will be an introduction to general techniques for developing and proving approximation guarantees of algorithms. This is followed by a series of different approximation algorithms for various problems from the area of graph algorithms.

List of Topics

1. Introduction: from NPO to APX
2. Introduction to Linear Programming Techniques for Approximation Algorithms
3. Set Cover
4. Sparsest Cut
5. Applications of Sparsest Cut; Balanced Cut
6. The Multicut Problem
7. The Multiway Cut Problem
8. Tree embeddings
9. An O(log n) Approximation for Minimum Bisection
10. Graph Partitioning Using Single Commodity Flows
11. The Steiner Forest Problem
12. Steiner Network
13. Euclidean TSP
14. Max Cut