Lecture Course "Approximation Algorithms"

Current information on regulations and recommendations concerning the coronavirus epidemic can be found on the pages of the Bachelor-Master Office Mathematics and the University of Bonn.

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 classcial NP-hard combinatorial optimization problems, including the TSP, set covering, knapsack, bin packing, and satisfiability problems.

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

• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, Sixth edition 2018 (Chapters 16 - 22)

• D.P. Williamson, D.B. Shmoys: The Design of Approximation Algorithms. Cambridge University Press, 2011
• V.V. Vazirani: Approximation Algorithms. Springer 2001
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation. Springer 1999
• D.S. Hochbaum (editor): Approximation Algorithms for NP-Hard Problems. PWS 1996

Prerequisites:	Combinatorial Optimization, in particular basic knowledge in graphs, linear programming, network flows, matching, and NP-completeness; see, e.g., Chapters 1-15 of the book by Korte and Vygen (see above)
Class Hours:	Tuesdays and Thursdays 14:15-15:45
Room:	Online using Zoom. The link to the zoom meeting can be found on eCampus. Please register on eCampus.
Exercise Classes:	Monday 12:15—13:45 starting April 27th.