Institut für Theoretische Informatik, Algorithmik

Seminar: Approximationsalgorithmen

Sommersemester 2008



Die Ausarbeitungen sind als Seminarband verfügbar.



The seminar is based on the book Approximation Algorithms by Vijay V. Vazirani [1].

We will focus on Part II: LP-based algorithms which includes the chapters: 12. Introduction to LP-Duality 13. Set Cover via Dual Fitting 14. Rounding Applied to Set Cover 15. Set Cover via the Primal-Dual Schema 16. Maximum Satisfiability 17. Scheduling on Unrelated Parallel Machines 18. Multicut and Integer Multicommodity Flow in Trees 19. Multiway Cut 20. Multicut in General Graphs 21. Sparsest Cut 22. Steiner Forest 23. Steiner Network 24. Facility Location 25. k-Median 26. Semidefinite Programming

The seminar aims at advanced students (Hauptstudium) who have solid previous knowledge in algorithms (e.g., Algorithmentechnik). Knowledge from the lecture Approximations- und Onlinealgorithmen will help but is not mandatory.

Participants will have to give a short presentation (10 minutes) about two weeks after the assignment of the topics, a detailed presentation on their topic during the block weekend in Baerenthal and write a concise summary (5-10 pages) to be handed in at the end of the term.

The seminar is a collaboration between Karlsruhe University and the TU Eindhoven, which offers students from both universities the possibility to practice giving a scientific presentation for an international audience.

After the seminar talks we will have time to do a hike around Baerenthal. See our previous Baerenthal seminars Randomisierte Algorithmen in der algorithmischen Geometrie and Approximationsschemata in Ablaufplanung, Graphentheorie und Geometrie.

Please register for the seminar by sending an email to Martin or Ignaz.