Advanced Topics in Approximation Algorithms Tobias Mömke

News

29.05.2020

IMPORTANT NOTICE - HISPOS

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!

14.05.2020

Material

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.

11.05.2020

Access Information for Zoom Meetings

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... 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.
 

08.05.2020

First Discussion on May 14

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.



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators