News
Final TalksWritten on 12.08.20 by Tobias Mömke On Thursday, August 13 starting at 10:00, the participants of the seminar will give their presentations, using a web whiteboard and/or Zoom Screen Sharing. |
Thesis TopicsWritten on 15.06.20 by Tobias Mömke I started a page with possible Master-Thesis topics related to the topics that we discuss (within "Information" in the menu). If you are interested, please contact me. |
IMPORTANT NOTICE - HISPOSWritten on 29.05.20 by Tobias Mömke As usual, students have to register their attendance to seminars in HISPOS within three weeks after the kick-off meeting. Please register in HISPOS no later than the deadline: Wednesday, June 3, 2020! |
MaterialWritten on 14.05.20 by Tobias Mömke I have added the whiteboard and a script to the Material-section (in the menu "Information"). The script contains many of the points that we were discussing today. |
Access Information for Zoom MeetingsWritten on 11.05.20 by Tobias Mömke When logged in, there is a new point "Zoom Meeting" in the menu "Information" which contains the link you need to join the meetings. The link will be the same for every meeting.
Additionally, there is a new point "Reading List." There we will keep track of the papers which we read in the… Read more When logged in, there is a new point "Zoom Meeting" in the menu "Information" which contains the link you need to join the meetings. The link will be the same for every meeting.
Additionally, there is a new point "Reading List." There we will keep track of the papers which we read in the seminar. Additionally, I started listing background material which may be helpful. |
First Discussion on May 14Written on 08.05.20 by Tobias Mömke The seminar discussions will take place every Thursday from 11:00 to 13:00, starting from May 14. |
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.
Requirements:
Students should have attended the core course "Optimization" or have acquired comparable basic knowledge about linear optimization.
Modalities:
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.