After successful completion of the course, students are able to...
- explain the difference between exact and approximative solutions
- analyze the approximation ratios of algorithms
- reproduce classical approximability results for discrete optimization problems
- understand published articles in the area of approximation algorithms
- Measure of quality for approximation algorithms
- Basic schemes of heuristics and methods to determine the approximation ratio
- Heuristics and their analysis for Bin Packing, Scheduling, Knapsack, TSP, Vertex Cover and Set Cover Probleme
After a successful completion of the course, students are able to understand the complexity respectively the approximability status of discrete optimization problems. Moreover, they have the theoretical basics for doing a worst-case analysis for a given approximation algorithm.
K. Jansen, M. Margraf, Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter, 2008.
R. Wanka, Approximationsalgorithmen: Eine Einführung, Teubner, 2006.
D.S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Company, 1997.
V.V. Vazirani, Approximation Algorithms, Springer, 2001.
G. Ausiello et al., Complexity & Approximation, Springer, 1999.