Sommersemester 2021

Unless otherwise announced this semester the Research Seminar will be held via video conference. If you would like to participate, you will receive the technical details from Matthias Fischer by e-mail.

Fabian Hoepfner

June 23, 2021, 2:00 (video conference)

About the Impact of Stationary Robots on Discrete Gathering Strategies

Swarms of small robots with limited capabilities, e.g.  without communication, offer some advantages over one larger robot.  In order to control theserobot swarms several algorithms are proposed by research, one of them being theGo-To-The-Centeralgorithm for gathering a swarm of robots in one location. Sincedistributed systems always have to deal with crash faults, we introduce stationaryrobots to the Go-To-The-Center in this thesis and analyse the impact on theirbehavior and the run time of the algorithm. For this we run simulations and prove a time complexity of Θ(n2+ log(e))for most cases.


Dr. Marten Maack

June 23, 2021, 2:45 pm (video conference)

(In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling

We consider variants of the restricted assignment problem where a set of jobs has to be assigned to a set of machines, for each job a size and a set of eligible machines is given, and the jobs may only be assigned to eligible machines with the goal of makespan minimization. For the variant with interval restrictions, where the machines can be arranged on a path such that each job is eligible on a subpath, we develop the first better than 2-approximation and an improved inapproximability result.

Furthermore, we consider restricted assignment with R resource restrictions and rank D unrelated scheduling. In the former problem, a machine may process a job if it can meet its resource requirements regarding R (renewable) resources. In the latter, the size of a job is dependent on the machine it is assigned to and the corresponding processing time matrix has rank at most D. The problem with interval restrictions includes the 1 resource variant, is encompassed by the 2 resource variant, and regarding approximation the R resource variant is essentially a special case of the rank R+1 problem.

We develop improved inapproximability results for the 2 resource, 3 resource, and rank 3 variant. Both the approximation result for the interval case and the inapproximability result for the rank 3 variant are solutions to open challenges stated in previous works. Lastly, we also consider the reverse objective, that is, maximizing the minimal load any machine receives, and achieve similar results.


Sören Möllers

May 05, 2021, 2:00 pm (video conference)

Hybrid Data Structures for Real-Time Ray Tracing of Dynamic Scenes

As ray tracing is increasingly used for real-time rendering, ray tracing systems require efficient space-subdivision schemes for rendering complex scenes within limited frame time. In the context of dynamic scenes and interactive applications these data structures have to be updated quickly because this needs to be done for each new frame. Instead of just rebuilding the structure every time, one can exploit the fact that many objects in the scene are static or only move by a certain amount from frame to frame: It is possible to only update certain parts while not modifying large portions of the structure. This promises to be faster than rebuilding the structure from scratch.

In preparation for my master's thesis, I discuss these issues in detail and present a hybrid data structure combining an object hierarchy with regular space-subdivision, which is planned to be modified to work with dynamic and interactive scenes in the thesis.


Simon Pukrop

April 21, 2021, 2:00 pm (video conference)

The unit Server-Cloud Problem

The server-cloud problem is a scheduling problem in which we have to schedule a task graph on a combination of a single owned machine (the server) and and infinite number of rentable machines (the cloud).

The objective in the model is to process the task graph in a given timespan, while minimizing the cost for renting cloud machines. (Or the other way around: Minimizing the makespan with a given budget).

We further explore the server-cloud problem by looking at a simplified version of it: The unit server-cloud problem, in which every communication delay and every processing time (on the server as well as the cloud) is equal to 1.

We will show that this seemingly easy problem is still NP-hard, and give a first outlook on (failing) approaches to find approximations for this problem.


Till Knollmann

April 14, 2021, 2:00 pm (video conference)

Don’t store Cola with Mentos! – Facilities with Conflicts

As we all know, mixing cola with mentos might result in some unwanted consequences. What we learn from this is that there are goods (commodities) which should not be stored together. We incorporate this simple fact into the Multi-Commodity Facility Location Problem. In the latter, there is a set of clients in a metric space, each requesting a set of commodities.

An algorithm has to connect each client to a set of facilities offering the respective commodities. The overall goal is to minimize the total cost induced by opening costs for the facilities (dependent on the location and the offered commodities) and by connecting clients to facilities (dependent on the distances between them).

We aim at analyzing the competitive ratio in an online setting where clients arrive over time and have to be immediately and irrevocably connected on arrival. When adding a so-called conflict where two or more commodities (e.g. cola, mentos) may not be offered within a certain distance to each other, the original model is no longer suitable.

In this talk we present how the model can be changed to allow for non-trivial solutions and we show first insights for algorithms with a low competitive ratio based on a linear program representation of the problem.