Sommersemester 2020

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.

Surender Baswana

May 27, 2020, 2:00 pm (video conference)

Title: Fault tolerant data structure for all-pairs mincut

Let G=(V,E) be an undirected unweighted graph on n vertices. We address the problem of quickly reporting the value of mincut between any pair of vertices upon failure of any edge. The only previous data structure for this problem is only for a fixed pair of source and destination vertices. This data structure takes O(n) space and O(1) query time, and dates back to 1980.

We present a fault tolerant data structure for all-pairs mincuts. It takes O(n^2) space and takes O(1) time to report (u,v)-mincut upon deletion of any edge (x,y) for any u,v\in V and (x,y)\in E.

Jan-Hendrik Bock

May 20, 2020, 2:00 pm (video conference)

Multi-Agent 3D Scene Generation

A 3D scene is an important part of many applications, one of which is video games. There is a huge number of video games that are being created and many of them use 3D worlds. Creating them by hand is often very time consuming. Having a tool to help generate at least a first scene that can be improved upon may be extremely helpful. Some games actually only use automatically generated worlds. This thesis has built a 3D scene generator that uses multiple agents to generate a 3D world. To achieve this multiple types of agents were developed to create different types of landscape, like mountains, rivers and cities. These agents work on the terrain in real-time and sometimes communicate with each other to generate the 3D world. This developed system was evaluated in multiple ways including a runtime analysis and a discussion about each agents strategy. In conclusion this thesis shows that 3D scene generation with multiple agents that communicate with each other works and it gives insight into what problems need to be solved to successfully create such a system. Agent systems can be very flexible with the number of features (like plantlife, cities or mountains) present for example, but their strategies grow more complex with each added feature that depends on already implemented strategies.

(Final Presentation Master's Thesis)

Simon Pukrop

May 13, 2020  - Due to illness the presentation is unfortunately cancelled.
It will take place in the next few weeks.

Server - Cloud Scheduling

In this model we consider scheduling on a single machine that is local (the server) and an unlimited number of (fast) remote machines (the cloud). Jobs are given as task graphs and switching between the different machines mid-job induces some communication delay on a contested communication channel.

We start by exploring the setting under the makespan criteria, that is processing task graphs as quickly as possible. We establish that this problem is NP-hard even under some limiting assumptions, and give some first insights in approximating this problem. Later we will take a look at a modification of the setting, where a job has to be processed before some deadline and we aim to minimize the (outsourced) time on the cloud.

Jonas Harbig

April 29, 2020, 2:00 pm (video conference)

Initial Presentation to the Master Thesis "Max-Chain-Formation Problem on a Grid"

We will analyze the Max-Chain-Formation problem on a two dimensional grid. It considers the following problem: Starting with a swarm of n robots which are initially connected in a chain we form a line of length Θ(n). Castenow et al. developed an algorithm for this problem in the Euclidean plane. Their model considers local robots which can observe a constant distance along the chain. In the fully synchronous FSYNC model they stated a quadratic running time while in the continuous model they provided an asymptotically optimal algorithm in O(n).

We will consider a similar local model on a grid where robots are anonymous, oblivious and have no global senses such as a compass or coordinate system. In our talk we will present the challenges of transfering the problem on a grid. We will further provide an algorithm for the problem on a one dimensional grid and prove a tight running time of Θ(n²).

(Introductory talk Master's Thesis)