# Oberseminar

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

#### July 18, 2020, 2:00 pm (video conference)

**A compact fault tolerant data structure for all-pairs Mincuts**

Let G=(V,E) be an undirected graph on n vertices and m edges where each edge has a unit capacity. We address the problem of designing a compact data structure that can answer the following query:

Mincut(u,v,e): Report the value of mincut between u and v upon the failure of edge e.

The only solution that exists for this problem is for a single pair of vertices only and dates back to 1980. The data structure takes O(n) space and achieves O(1) query time. We present an extremely compact solution for the all-pairs version of this problem. Our data structure occupies O(m) space only and it can answer any query in time O(min(m,nf)) where f is the value of mincut between the query vertices. On the way to achieve this result, we also present an O(n^2) space data structure for this problem that takes O(1) query time.

##### Gleb Polevoy

#### July 1, 2020, 2:00 pm (video conference)

**Hiders' Game**

Various problems in adversarial social network analysis involve some members of a network attempting to evade social network analysis tools, e.g., centrality measures, community detection, or link prediction algorithms. While most works focus on unilateral actions of (an) evader(s), we propose here the first analysis that is based on a network formation game. In particular, the newcomers in our model attempt to connect to and possibly to rewire the exiting social network, aiming to become directly tied with the players of high centrality but while keeping their own centrality small. Our model extends the existing network formation literature, including the model of Jackson and Wolinsky, by considering additional strategies and utility functions.

We algorithmically demonstrate that in such a game, the pairwise Nash stable networks (\PANS) constitute a lattice, where the stronger \PANS{} constitute a lattice nested in the weaker \PANS. Given this, we prove that inclusion in \PANS{} implies less utility. Furthermore, we bound the social efficiency of \PANS{}---namely the price of anarchy and stability---and directly connect efficiency to the strength of \PANS.

Finally, we exactly characterise the \PANS{} in practically important settings.

##### Michael Erjemenko

#### July 1, 2020, 2:45 pm (video conference)

**Max-Line formation with highly limited robots in thee continous time model**

Since small mobile robots become inexpensive the tendency increased to exchange big, powerful and expensive systems by several lightweight, simple and cheap robots. Amongst other possible tasks, such swarms can be used to enable communication by providing fields or chains of mobile relays. Because of the desired simplicity of such robots, no ensured initial placement and a variety of setting definitions the problem of building communication formations has still many open questions and is therefore an interesting research field.

This Master's Thesis focus on the problem of forming a maximum long line of robots (Max-Line formation problem) and refers with that to the current research of the Algorithms and Complexity group of the Heinz Nixdorf Institute which considers the Max-Chain formation problem. The presentation will introduce two of the three developed algorithms, a theoretical analysis for the first algorithm and the evluation results for the second. Although the second algorithm has a simple form it achieves in averge a nearly optimal runtime and handles almost every problem instance. This work is, to our knowledge, the first that deals with the Max-Line formation problem to this extent.

(Final Presentation Master's Thesis)

##### Christian Soltenborn

#### June, 24, 2020, 2:00 pm (video conference)

**Introduction to KI Marktplatz**

The KI-Marktplatz is a project aiming at bringing together small and medium sized companies with providers of AI solutions and academia. The goal is to help companies increase their productivity and competiveness by making it much easier to apply AI technologies, in particular during the initial process of product creation.

In this talk, I will give an overview of the KI-Marktplatz project, and I will show very first ideas for applying technologies to the KI-Marktplatz which have been developed as part of the SFB901 and implemented by the "Proof of Concept" project.

##### Sascha Brandt

#### June 17, 2020, 2:00 pm (video conference)

**Surfel Cluster Rendering **

In this talk I will discuss our current research progress on a hybrid point/triangle rendering algorithm for complex scenes. The main idea is to use our progressive farthest-point sampling algorithm to cluster a 3D-polygonal-object into a set of small triangle clusters that are each associated to one sample point. During a virtual walk-through, we then render surfels for distant objects and switch to triangle clusters as we move closer. We can leverage the new Turing architecture of current GPUs to efficiently cull entire clusters during rendering. I will also briefly discuss how we could use a similar idea to build surfel hierarchies for large complex scenes.

##### Jannik Castenow

#### June 10, 2020, 2:00 pm (video conference)

**Closed Chain Gathering in Linear Time**

In this talk, we study the gathering of mobile robots with limited visibility in the Euclidean plane in the FSYNC time model (robots operate in fully synchronized rounds). The robots are connected in a closed chain topology. Limited visibility means here that two direct neighbors of the chain have to be in distance less or equal than one and that a robot can only see a constant number of its closest chain neighbors. We allow the robots to store a constant number of visible states (lights) that can be perceived by the neighboring robots. Our strategy basically consists of two main parts – a strategy for highly symmetric configurations (isogonal configurations) and a strategy for asymmetric configurations. In the latter configurations, the visible states are used to sequentialize the movements of robots similar to the Hopper strategy for Chain-Formation in FSYNC. In highly symmetric configurations these states cannot be used since – due to the symmetric views of the robots – no starting points for such a sequential movement can be identified. We characterize isogonal configurations and propose a strategy to gather these in linear time. The combination of both strategies, i.e. robots with highly symmetric local views execute the strategy for symmetric configurations and all other robots execute the strategy for asymmetric configurations, allows us to gather all configurations in linear time.

##### Till Knollmann AND Simon Pukrop

#### June 03, 2020, 2:00 pm (video conference)

**The Online Multi-Commodity Facility Location Problem (Till Knollmann)**

We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \( S \) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the Multi-Commodity Facility Location Problem (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of \( S \). A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each.

To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \( \Omega ( \sqrt{|S|} + \frac{\log n}{\log \log n} ) \) that already holds for simple line metrics. Here, \( n \) is the number of requests. On the other side, we establish a deterministic \( O (\sqrt{|S|} \cdot \log n) \)-competitive algorithm and a randomized \( O (\sqrt{|S|} \cdot \frac{\log n}{\log \log n} ) \)-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function.

**Server - Cloud Scheduling (Simon Pukrop)**

In this talk we take a look at a new scheduling model. 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.

##### Surender Baswana

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

**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)