Seminar SS2022

Dynamic Algorithms

Dynamic Algorithms banner

Contents

In many problems that you might know, the correct input is given in advance and you can calculate a solution for the problem. This can happen for example in a routing problem, where you try to find a shortest path on a map between two given points.

Now imagine you have calculated an optimal route, and have already started travelling: At some point, maybe a street is blocked or there is some delay due to traffic congestions. What can you do now?

Of course you can use your algorithm and calculate a new route, starting at zero. But is there maybe also a possibility to use some of the results that you have already calculated at the first attempt of finding a route?

These kind of problems are the so called "dynamic problems", and in this seminar we will talk about exactly those (and of course about algorithms, that handle in this setting).

Further examples of those problems can be found easily in every-day life, but for example also on Wikipedia

Date and Time

The seminar will be held on a weekly basis. We expect you to actively participate during the presentations, e.g. asking questions and activating your camera, if the seminar is held online (if the seminar is not held online, questions and feedback will also be expected of course).

The date of the kickoff-meeting will be announced before the start of the summer semester. The regular date and time will be announced after the topics are distributed.

Note that participating in this seminar requires a registration on Supra!

Material

Dates and Topics

The presentations start on May 5th. We meet Thursdays every week at 12:30 in the seminar room of the i1 except for holidays.
Date Topic
 Student
May 5th
 Connectivity on undirected graphs Beka
May 12th
 Minimum weight spanning tree Lea
May 19th
 Cycle Detection + Topological Ordering Vincent
June 2nd
 Matching Xiaolu + Haihua
June 23rd
 Motif counting Jakob + Maxim
June 30th
 Diameter Gerrit
June 30th
 Reoptimzation of Steiner trees Linus
July 7th
 On the Approximability of TSP on Local Modifications of Optimally Solved Instance
(Room 9222 in E3) 		Lasse
July 14th
 Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time Tianjun