Research Institute for Discrete Mathematics

Lecture Course "Approximation Algorithms"

Summer term 2021

(Module V4C2 and MA-INF1201)

Approximation algorithms are polynomial-time algorithms that guarantee to find a feasible solution that is optimal up to a factor of k. For some NP-hard problems, k can be chosen arbitrarily close to 1, for others there is a best possible constant, and for some problems there is no such constant (unless P=NP). We analyze the approximability of various classical NP-hard combinatorial optimization problems, including the TSP, set covering, knapsack, bin packing, facility location, and satisfiability problems.

This course will be in English. Most of the course will be based on the following book:

The following textbooks can also be recommended: All these books are available in our library.

If you would like to participate, please register for this course on eCampus.

Prerequisites: Combinatorial Optimization
(in particular basic knowledge in graphs, linear programming, network flows, matching, and NP-completeness; see, e.g., Chapters 1-15 of my textbook above)
Class Hours: Tuesdays and Thursdays 14:15-15:45
Zoom link: See e-Campus.
Exercise Classes: Jannis Blauth, Mondays 16:15-17:45, see eCampus
Exams: Oral exams have been scheduled on July 29/30 and September 30.

Professor J. Vygen