NewsCurrently, no news are available
Advanced Topics in Approximation Algorithms
Given an NP-hard optimization problem, we cannot guarantee to find an optimal solution efficiently. At the same time, many practically relevant problems are NP-hard. What is the shortest way to deliver parcels to customers? Which tasks should be scheduled on a satellite with limited power resources in order to maximize the number of tasks executed?
In approximation algorithms we determine the amount of deviation from optimality needed in order to ensure polynomial time (i.e., efficient) computations. It is exciting and challenging to understand the approximability of fundamental optimization problems. In this seminar we will be concerned with up-to-date research topics in the field of approximation algorithms.
More specifically, the seminar will focus on the use of linear programming in the context of approximation algorithms. We will cover topics including primal-dual algorithms, randomized rounding, and iterated linear programming.
Students should have attended the core course "Optimization" or have acquired comparable basic knowledge about linear optimization.
The seminar is research oriented. The papers to be read will be challenging. To acquire a deep understanding of these papers and the topic overall, we will have weekly informal meetings during the semester where we will discuss the contents of the papers and possibly discuss how the techniques can be used for open research problems.
At the end of the seminar (after the lecture period of the summer term 2020), each participant will give a presentation which summarizes the knowledge obtained during the semester.
The seminar has 7 credit points.