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

#### October, 13, 2020, 2:00 pm, Room: F0.225 (video conference)

Die exponentielle Zeit Hypothese

Alle bekannten und nichttrivialen Algorithmen für das NP–vollständige Problem haben eine exponentielle Laufzeit. Daher wird vermutet, dass dieses Problem nicht in subexponentieller Zeit $poly(n)\cdot 2^{o(n)}$ entscheidbar ist, wobei $n$ die Anzahl der Variablen in der booleschen Formel ist. Diese Vermutung wird **die exponentielle Zeit Hypothese (EZH)** genannt. In dieser Arbeit wird diese Hypothese und ihre Auswirkung auf andere NP–vollständige Probleme untersucht. Ein Beispiel eines exponentiellen Algorithmus für $k$–SAT ist der Algorithmus von Monien und Speckenmeyer, welcher in dieser Arbeit ebenfalls im Detail betrachtet wird. Der Algorithmus hat Laufzeit , wobei $\alpha_k$ die größte Zahl ist, so dass $\alpha_k=2-\frac{1}{(\alpha_k)^{k-1}}$ gilt. Für $k=3$ ist $\alpha_3=1,6181$ und die Laufzeit ist $\mathcal{O}(poly(n)\cdot 1,6181^n)$.

Ein wichtiges Ergebnis, das wir beweisen, ist das Sparsification Lemma. Das Lemma zeigt die Existenz eines Algorithmus, der für beliebige $\varepsilon > 0$ eine beliebige boolesche Formel in Form in eine Disjunktion von $2^{\varepsilon n }$ $k$–KNF Formeln modifiziert, so dass jede dieser Formeln nur $\mathcal{O}(n)$ Klauseln hat. Wir zeigen, dass aus diesem Lemma eine größere untere Schranke für $k$–SAT unter der EZH folgt: $k$–SAT hat keinen Algorithmus mit Zeit$\mathcal{O}(poly(n+m)\cdot 2^{\varepsilon (n+m)})$, wobei $n+m$ die Anzahl der Variablen und Klauseln in der booleschen Formel ist. Mit Hilfe dieses Ergebnisses werden untere Schranken für einige NP-vollständige Probleme bestimmt.

Es werden folgende NP-vollständige Probleme betrachtet: Das Knotenüberdeckungs-, das gerichtete Hamiltonkreis-, das 3-Färbbarkeits- und das unabhängige Menge-Problem. Es wird gezeigt, dass diese Probleme unter der EZH keinen subexponentiellen Algorithmus, also keinen Algorithmus mit Zeit $poly(n+m)\cdot 2^{o(n+m)}$, haben, wobei $n+m$ die Anzahl der Knoten und der Kanten im Graphen ist.

Außerdem werden NP–vollständige Probleme in planaren Graphen betrachtet: Das planare , das planare Knotenüberdeckungs-, das planare unabhängige Menge- und das planare Hamiltonkreisproblem in gerichteten und ungerichteten Graphen. Für diese Probleme wird eine kleinere untere Schranke bestimmt: Es wird gezeigt, dass diese Probleme unter der EZH keinen Algorithmus mit Zeit $poly(n+m)\cdot 2^{o(\sqrt{n+m})}$ besitzen, wobei $n+m$ die Anzahl der Knoten und Kanten ist.

Abschließend wird ein subexponentieller Algorithmus mit Zeit $2^{\mathcal{O}(\sqrt{n})}$ für das NP–vollständige Problem unabhängige Menge in planaren Graphen entwickelt.

#### September, 29, 2020, 09:00 am (video conference)

Linienformation einer Roboterkette: Untersuchung zur Konvergenz

Bei einem Such- und Rettungseinsatz sollen Roboter ein Gebiet absuchen. Um dabei keinen Bereich doppelt zu durchsuchen oder undurchsucht zu lassen, bewegen sich alle Roboter in dieselbe Richtung und bilden orthogonal zur Bewegungsrichtung eine Kette mit maximaler Länge, sodass die Roboter ebenfalls in Bezug auf ihre Sichtweite maximalen Abstand zueinander haben. Das Aufstellen der Roboter in dieser Formation ist das Maximumchain Problem aus dem Gebiet der Schwarmrobotik.

Ein schlichter und intuitiver Lösungsansatz dafür ist die bekannte Bewegungsstrategie Max-Go-To-The-Middle, die jedoch das Ziel in einigen Situationen langsam und in anderen gar nicht erreicht. In diesem Vortrag werden die Bedingungen zu diesem Verhalten für spezielle Aufstellungen der Roboter angegeben, in denen sich alle Roboter auf einer Geraden befinden oder die erste und zweite Hälfte der Roboter paarweise auf derselben Position stehen. Zusätzlich wird per Simulation die Existenz allgemeinerer Aufstellungen mit diesem Verhalten nachgewiesen und gezeigt, dass ein Zusammenhang zwischen diesen und langsamen Aufstellungen besteht.

Des Weiteren werden zwei abgewandelte Versionen der Max-Go-To-The-Middle Strategie vorgestellt und miteinander verglichen. Durch diese Anpassungen kann das schlechte Verhalten der ursprünglichen Strategie mit einer der abgewandelten Strategien reduziert und mit der anderen nahezu beseitigt werden.

#### September, 23, 2020, 2:00 pm (video conference)

Generating multi-LOD Objects using Inverse Procedural Modelling

More and more applications use virtual scenes. Often, these scenes should be realistic. Together with the desire for larger scenes there are two challenges. The rendering becomes more complex due to the detailed objects and more objects are needed to fill the worlds.

To create content automatically, Procedural Modelling systems can be used. Thereby, the computer generates objects based on rules given by an expert using the system. Inverse Procedural Modelling techniques are used to automate the rules creation process, by infering them from input models.

The rendering process is optimized by using Level of Detail systems that reduce the complexity of objects in the scene.

In this talk a novel approach to generate houses in different LODs using Inverse Procedural Modelling techniques is presented. The approach is explained, and results are examined using an implemented prototype. This prototype delivered promising results for various models. The approach thus combines both the creation of realistic models and a more efficient rendering of objects in real-time scenarios

#### September, 18, 2020, 11:00 am (video conference)

Max-Chain-Formation Problem on a Grid

We study the swarm coordination problems Chain-Formation and Max-Chain-Formation on a two-dimensional grid. To achieve a Chain-Formation, $n$ robots ordered in an open chain with fixed endpoints have to form a minimal connection between both endpoints. For a Max-Chain-Formation the chain must maximize the distance between its endpoints (which naturally can be moved in this scenario).

Our robots act according the OBLOT model under fully-synchronous FSYNC scheduling. They are identical, anonymous, oblivious, silent, homogeneous and autonomous. Furthermore, the robots are disoriented, i.e. neither have a common sense of direction nor share a coordinate system, and have a limited visibility. In our thesis it is shown that it is not possible to reach an optimal result in general for any of the problems under this model. Instead, we consider only $\Theta(1)$-approximations of the optimum.

We provide an algorithm which solves the Chain-Formation in $\calO(n^2)$ rounds. In the end, the chain has a length of at most $3 * Outer-Robot-Distance$ (the distance between both endpoints of the chain measured in $L^1$). We extended this algorithm in order to achieve a Max-Chain-Formation as well. Similar to a known algorithm on the Euclidean plane , the result differs for two classes of initial configurations. Applied to an Opposed-Configuration, where both ends of the chain point in different directions, after $\Theta(n^2)$ rounds the Outer-Robot-Distance is at least $n/6$. The other class is a Marching-Configuration, for which it is possible that the whole chain moves infinitely in one direction without ever reaching a Max-Chain-Formation.

#### August, 26, 2020, 2:00 pm (video conference)

Spectral Gap and Optimal Weighting of the Multiplexed Metropolis Light Transport Algorithm

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

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

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

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

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

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

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

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

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

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

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