### Quick access

# Research Seminar

## Summer Term 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.

##### Sascha Brandt, Matthias Fischer, André Graute, Jan-Luca Hansel, Roman Meusch, Sören Möllers

#### July 7, 2021, 2:00 pm (video conference)

**The virtual laboratory "DigiChemLab" **

In cooperation with the Department of Chemistry at the Paderborn University, we are developing a VR system for the implementation of virtual learning units in chemistry lessons in a project funded by the DAAD. The VR system consists of a VR headset with which chemistry students can conduct experiments in a virtual laboratory. Virtual objects can be grasped and moved, liquids such as water and chemicals such as sodium can be mixed in a beaker with the help of a magnetic stirrer. This gives the students of our project partners in China the opportunity to conduct their first experiments in a laboratory even before they have arrived here in Paderborn for their studies abroad. We present the current implementation status of the virtual laboratory "DigiChemLab".

**AND**

##### Gleb Polevoy

#### July 7, 2021, 2:45 pm (video conference)

**Fair, Individually Rational and Cheap Implementation**

We handle the problem of inefficient and multiple Nash equilibria by subsidies and taxes, leading to a game with a single and efficient equilibrium. This allows coordination on a communication protocol, a common language or an investment strategy.

Inspired by the seminal work of ~\cite{MondererTennenholtz2004}, where the promised subsidies do not materialise in the non-dominated strategies, we provide a fair and individually rational game adjustment, such that the total investment from outside sum up to zero for any profile, thereby facilitating easy and frequent usage of our adjustment without risking costs even if some players behave unexpectedly. The unique equilibrium is not adjusted. We also consider incomplete information scenarios, while minimising the total transactions.

##### (Joint work with Marcin Dziubiński)

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

**AND**

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