Research Institute for Discrete Mathematics

Lecture Course "Selected Topics in Discrete Mathematics"

Modern Rounding Methods for Approximation Algorithms

Summer term 2016

(Module V5C2)

A c-approximation algorithm is an efficient algorithm that produces feasible solutions for a given problem whose value is within a factor c of that of an optimum solution. A key step in designing good approximation algorithms is to find a high-quality bound on the value of an optimum solution. In this course, we will focus on bounds obtained through mathematical programming relaxations, and on how to round these into feasible solutions for the given problem.

Most of the topics to be discussed will be recent (i.e., from the past 5 years), and the course will therefore predominantly rely on research papers. Topics to be discussed will include:

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. Some familiarity with the basics of approximation algorithms (e.g., Chapter 16 of Korte & Vygen) may be useful.

Time: Wednesday, 2-4pm
Room: Gerhard-Konow-Hörsaal, Lennéstr. 2


Lecture Notes

Throughout the term, I will be posting handwritten lecture notes. The plan is to post the notes ahead of the lecture. Please let me know if you spot glaring errors, and I will do my best to correct.

Professor J. Könemann