Unit 10: Approximation Algorithms

This unit covers

• approximation algorithms using several examples:
  • Vertex Cover
  • Set Cover
  • Traveling Salesperson Problem
• (F)PTAS

Material

— to be added —

Further reading and sources

The presentation mostly follows

• Vazirani, Vijay V. “Approximation Algorithms.” Springer, 2001.

Examples are also taken from Advanced Algorithms, following the module in Kaiserslautern initially developed by Markus Nebel.

---

Unit 9  ⋅  Syllabus  ⋅  Unit 11