# Winter Term 2016/17

#### March 29, 2017, 2:00 pm, F1.110

Robust Optimization in Congestion Games

We will discuss a way to represent data uncertainty in atomic congestion games. Therefore we will describe and formally define three different models of atomic congestion games that can depict failing resources, which will influence the cost and choices of the egoistic players in different ways. Also we will test and proof if those models still hold the nash equilibrium property of classic congestion games. Finally there will be a mention of the possibilities and limitations our new definitions yields for modelling different use cases.

(Final Presentation Bachelor's Thesis, talk in German)

#### March 29, 2017, 2:30 pm, F1.110

Sorting of Dynamic Data

In this thesis we consider the sorting problem for the dynamic data model, published by Anagnostopoulos et al. \cite{Dynamic}. In the dynamic data model we have a data set and an underlying global order. In each timestep the global order is modified by an adversary, who swaps a pair of elements in the order. Goal of a sorting algorithm is to estimate the global order of the data set in each timestep. In each timestep the sorting algorithm can only comapare a limited number of elements. Main goal of this thesis is the comparison of three sorting algorithm for three adversaries in the dynamic data model. Therfore we implemented a simulation tool to simulate and evaluate the sorting algorithms. The results of the simualtions will be presented in this thesis.

(Final Presentation Bachelor's Thesis, talk in German)

#### March 22, 2017, 5:00 pm, F1.110

Active Learning of User Requirement Specifications in Dynamic Software Service Markets

Im meiner Arbeit beschäftige ich mich im Kontext des SFB 901 - On-The-Fly Computing damit, wie der bisherige evolutionäre Ansatz für die semi-automatisierten Anforderungserhebung verbessert werden kann. Eine besondere Herausforderung ist dabei die geringe Menge der Daten. Durch die Kombination der Konzepte "interaktive evolutionäre Algorithmen", "Co-Evolution" und "aktives Lernen", wobei das Orakel durch den Benutzer verkörpert wird, konnte der bisherige Ansatz zum Teil signifikant verbessert werden.

(Final Presentation, Master's Thesis)

#### March 7, 2017, 2:00 pm, F1.110

Evolving Self-Organizing Behaviors in Groups of Autonomous Agents by Minimizing Surprise

(Final Presentation, Master's Thesis)

#### February 22, 2017, 2:00 pm, F1.110

Continuous Monitoring of Distributed Data Streams for Partitioning Problems

Continuous monitoring of distributed data streams attracts attention in recent years. We are interested to analyze the following partitioning problem in the context of sensor networks. Each node is given a position on a line and observes values that may change over time. There is one server who is asked to compute a disjoint partition of the line into intervals, so that the values currently observed by the nodes of each interval differ at most by a predefined error bound. The goal is to maintain such a partitioning in intervals over time without changing the intervals too often. We are optimistic that  filter-based algorithms are promising for a competitive analysis. This problem might be  of interest to solve approximated variants of classical monitoring problems, i.e. \textit{Top-}$k$, \textit{Heavy Hitters} or \textit{Frequencies}.

#### February 8, 2017, 2:00 pm, F1.110

Controlling Palletizers

In delivery industry, parcels and bins have to be stacked-up from conveyor belts onto pallets with respect to customer orders. This is done by so-called palletizers which are offered by various manufacturers. The bins are picked-up iteratively by stacker cranes or robotic arms and are moved onto pallets, which are located at stack-up places. Each pallet has to contain bins destined for one customer to avoid re-sorting during delivery by trucks. Bins with different pallet labels have to be placed on different pallets, bins with the same pallet label have to be placed on the same pallet. Full pallets are carried away by automated guided vehicles, or by another conveyor system, while new empty pallets are placed at free stack-up places. The number of available stack-up places is limited.
The developers and producers of robotic palletizers distinguish between single-line and multi-line palletizing systems. In single-line palletizing systems there is only one conveyor belt from which the bins are picked-up. Several robotic arms or stacker cranes are placed around the end of the conveyor. We have modeled such systems by a random access storage which is automatically replenished with bins from the main conveyor. In multi-line palletizing systems there are several buffer conveyors from which the bins are picked-up. The robotic arms or stacker cranes are placed at the end of these conveyors and each arm can only pick-up the first bin of the buffer conveyors. Such FIFO palletizing system can be modeled by several simple queues.
In the talk we analyze the time complexity of the stack-up problem, we present some digraph models to solve the problem exactly, and we give two integer programming models. The strong relation to the pathwidth problem allows an approximation algorithm with error bound logarithmic in the number p of stack-up places. We will discuss some extensions of our models and some topics of future research.

(jointed work with Frank Gurski, Heinrich-Heine-University Düsseldorf)

#### February 1, 2017, 2:00 pm, F1.110

A Simple Gathering Algorithm for Robots on a Grid

We research strictly local gathering algorithms for point shaped, fully synchronous robots (FSYNC time model) on a grid. Within this model, we recently have published two results that are both asymptotically optimal concerning the total running time. More precisely, our strategies need just O(n) rounds for completing the gathering task for a connected swarm of n robots. These strategies are quite complex and the robots need additional strong capabilities like a constant number states visible to neighboring robots, local communication, and are non oblivious. Currently, we are developing a strategy that does not require the emphasized strong robot capabilities and moreover is rather simple. The price for this is a much worse total running time of O(|swarm's outer boundary|^2)\subset O(n^2) many rounds, but we suspect that this upper bound might also be tight for the restricted robot model in general.

#### January 31, 2017, 2:00 pm, F1.110

Binary Collective Decision-making with Long-term Adaptation System on Braided Compounds

Swarm robotics is an approach to the coordination of a large number of autonomous simple robots with local communication and local knowledge. The robots interact with each other and the environment in the process of performing tasks collectively. Therefore, collective decision-making is one of the essential collective tasks that robots are designed to accomplish. Collective decision-making is a challenging component in the swarm systems because the quality degree of the consensus is the basis for many other collective behaviors of the swarm. The collective decision-making becomes more challenging when the robots are stationary and incapable of moving through the swarm in order to gather information distributed in the swarm. In bio-hybrid systems, there are robots which are designed to be stationary and equipped with simple electronic units including communication units, processing units, sensors, the collective decision-making task is a problem which needs to be resolved. The field has open problems. The problem that we are working on in this thesis is the binary collective decision-making process based on the local majority rule for the swarm of stationary robots equipped with ambient light sensors. We show that the collective decision-making process based on the local majority rule is ineffective in some scenarios. Therefore, we extend the process with a long-term adaptation system which considerably improves the effectiveness and the efficiency of the process.

(Final Presentation, Master's Thesis)

#### January 18, 2017, 2:00 pm, F1.110

Congestion Games with Complementarities

We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.

#### January 11, 2017, 2:00 pm, F1.110

Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time and are to be scheduled on a single machine so as to minimize the maximum flow time. The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type. We study the online variant of this problem and focus on the non-clairvoyant case, i.e., the processing time of a job is only known upon its completion.
In the talk, we discuss some first results concerning a natural FIFO-based strategy, which is only $\Theta(\sqrt{n})$-competitive in the worst case, and give a first idea how we can obtain an improved bound in case processing times dictated by the adversary are slightly perturbed at random.

#### December 14, 2016, 2:00 pm, F1.110

Experimental Evaluation of a Gathering Strategy for Robots on a Grid

The presentation deals with a strategy to gather a connected swarm of pointshaped robots on a grid introduced in [1]. The strategy takes time of O(n), where n is the number of robots, and these robots only need limited capabilities. Utilizing a newly created simulator several experiments were performed to evaluate the strategy. The results are presented during this presentation. It is examined how the algorithm works if only the outer boundary of the swarm has to be connected. Additionally, it is evaluated how the strategy is affected by letting runners, that reshape the swarm, continue when they hop onto an occupied cell. This change has the effect that the running time only depends on the diameter and not on the total number of robots. Another experiment shows how changing the viewing radius and the run start interval L alters the running time. The value L determines how often runners are started to reshape the swarm. While a greater viewing radius decreases this time, a greater value for L slows the algorithm down. Additionally, it can be seen that a viewing radius greater than the run start interval hinders the pipelining. Nevertheless, the run passing operation is described in more detail and the strategy's constants are determined accordingly. The resulting viewing radius is 19, the run passing distance is 7 and L is 23.

[1] Andreas Cord-Landwehr, Matthias Fischer, Daniel Jung, Friedhelm, Meyer auf der Heider. Asymptotically Optimal Gathering on a Grid. 2016.

(Final presentation Bachelor's thesis, talk in German)

#### December 14, 2016, 2:30 pm, F1.110

Parallelization of algorithms for IR aerial image analysis of hardwood mixed stocks for the verification of the spread of oak damage

In my talk I will focus on the question, how dead trees can be identified using infrared pictures of an oak forest. Therefore, a technique used to analyze digital imagery is presented, applied to an exemplary forest and afterwards evaluated. Dealing with the problem of high hardware requierements a self-developed method is introduced that makes it possible to apply the discussed technique to arbitrary big forest areas. This method makes use of a parallel algorithm and a computer cluster to distribute the calculations on an arbitrary number of computers. The implementation that uses Hadoop and Spark is presented as well as evaluated.

(Final presentation Bachelor's thesis, talk in German)

#### December 7, 2016, 2:30 pm, F1.110

Almost surely collisionless gathering

In this talk we are going to consider the gathering problem for the group of mobile robots on Euclidean plane in continuous time and motion model. For this model we have proposed Go-To-The-Gabriel-Center (GTGC) algorithm and have shown that this algorithm gathers robots without early collision in 1D in time $\Theta(n)$. For 2D we have shown that the gathering is solved in time $O(n^2)$ with GTGC algorithm. We also conjectured that the gathering with GTGC is collisionless from almost every initial configuration. This conjecture turned to be very hard to prove. We relax the continuous time and motion model in the following way. In the relaxed model we assume that: robots are equipped with sources of randomness, some very limited memory and vision range extended by small positive constant. Within this relaxed model we present Jump-To-The-Gabriel-Center (JTGC) algorithm and show that this algorithm in the relaxed continuous model almost surely gathers robots without collisions in time $O(n^2)$.

#### December 7, 2016, 2:00 pm, F1.110

Strategic Online Facility Location

This talk summarizes our results in a strategic variant of facility location. Similar to the original model, clients have requests which incure costs equal to the distance to the nearest facility. New facilities are paid for by the clients who act as selfish players and may submit sealed bids to any location in the underlying network. If the sum of bids on a location is greater or equal the costs of the corresponding facility, it will be opened. We classify the overall costs of the game if every player invokes an online algorithm compared to a centralized offline solution which knows the requests in advance. We give an explicit strategy for all clients which is an equilibrium and has an overall good performance if the costs for the facilities are fixed. This talk is a preview of the upcoming presentation of the paper at COCOA 2016.

#### November 30, 2016, 3:00 pm, F1.110

Soft Growing Robots: the concept of soft braided robotic filaments in a bio-hybrid system

Continuous robot structures that grow or decline as opposed to modular robots, lend the opportunity for building incredibly flexible and deformable robot structures. Our EU project, flora robotica, craves a bio-hybrid system where robots and plants coexist in a symbiosis. Their coexistence demands a design of the robotic elements to be soft and flexible; robots that can grow (i.e., braiding) or decline (i.e., unbraiding). In our approach, a separate set of robots with the help of human users will support the braiding process. The level of softness in these robots can be due to the growth stage and may differ locally in the structure. These flexible filaments will have sensors/actuators embedded to support the well-being of the plant and monitor the growth process, as well as controlling the dynamics of their own structure. The talk will focus on our share in designing these robots; the past and the vision.

#### November 30, 2016, 2:30 pm, F1.110

Modular-width: An Auxiliary Parameter for Parameterized Parallel Complexity

Numerous graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be FPT when restricted to bounded treewidth but become W-hard when generalized to clique-width. Recently, Gajarsky et al. proposed a new parameter called modular-width defined using the notion of modular decomposition of graphs and showed that the chromatic number problem and the partitioning into paths problem are FPT when parameterized by this parameter. We study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are FPPT when parameterized by this parameter.

#### November 30, 2016, 2:00 pm, F1.110

Highly scalable procedural road generation on 3D terrains

In this thesis I propose a method for the procedural generation of roads on top of 3D terrains using a weighted shortest path algorithm. A path connecting a start and an end point is computed and used as the backbone for a drivable road. The nodes for the search graph are sampled from the discrete representation of the terrain. In order to achieve better scalability, the path is calculated using the underlying terrain mesh at its rendered LOD and is iteratively refined as the viewer changes his/her position in the environment.

(Final Presentation Master's Thesis)

#### November 25, 2016, 4:00 pm, F0.530

Christmas Seminar

Patrick Briest and Benjamin Eikel will give a talk. Both are former employees of the working group of Friedhelm Meyer auf der Heide (research group Algorithms and Complexity).
In 2007, Patrick Briest obtained his doctorate at TU Dortmund University. Now, he works as consultant at McKinsey in Düsseldorf. He will report on his field of activity.
In 2013, Benjamin Eikel obtained his doctorate at Paderborn University. Now, he works as software consultant at achelos GmbH in Paderborn. He will report on selected projects in the eHealth sector and in security testing.

#### November 23, 2016, 2:00 pm, F1.110

Complexity of Signalling in Routing Games under Uncertainty

It is common that self-minded drivers are informed over the congestion on the road via traffic reports; the question is if this actually improves traffic flow and reduces average travel time. The problem of the appropriate way to inform agents is known as signalling and the knowledge about signalling in routing games is comparatively limited hitherto. The aim is to extend the knowledge about signalling in routing via a theoretical analysis of routing games with uncertain demands or uncertain network latencies respectively. This encompasses the complexity and computability of signalling for uncertain demand single commodity networks; non-discrete uncertain demands; and (limited) uncertain link latency functions. The work is supposed contribute to the research area of signalling and might create the foundation for future research.

(Introductory presentation Master's thesis)

#### November 16, 2016, 2:00 pm, F1.110

Über die Rolle von Informationen in Verkehrsnetzwerken

We consider the following model of traffic networks. The road network is modeled by a flow network in a directed graph where every edge has a latency function that describes the cost of the edge depending on the flow that uses the edge. Additionally there is at least one vertex pairs (s, t) called commodity. To every commodity belongs a discrete probability distribution for the demand, i.e. how much flow needs to get through the network from s to t. We assume that the flow selfishly chooses the shortest available route which can lead to inefficient allocations of the network.
To avoid these inefficiencies we present the signaling which influences the flows knowledge of the demand probabilities such that the flow chooses other routes and the costs of the flow are lowered. We analyze in two networks how much the signaling can improve the costs. Furthermore we prove that finding the optimal signaling strategy in networks with two or more commodities is a NP complete problem.

(Final Presentation Bachelor's Thesis, talk in German)

#### November 16, 2016, 2:30 pm, F1.110

New results for scheduling with shared resources

In my talk, I consider a variant of scheduling on shared continuous resources. Here, a number of jobs with a certain resource requirement is given. They have to be scheduled on a number of m processors in order to minimize the makespan. I talk about a new result where the length of jobs may be arbitrary and we can give an algorithm with an approximation factor of approximately 2. Also, I discuss the impacts of this algorithm on the unit-size problem and the online problem (with unit-size jobs), where for the latter we still have some issues.

#### November 16, 2016, 3:00 pm, F1.110

Quality Measures for Algorithms that Monitor Distributed Data Streams

In this talk we consider different quality measures for algorithms that maintain a given solution over multiple time steps. In our previous work, it turned out that competitive analysis leads to a measure with a focus on instances that change 'smoothly'. However, it is also of interest to find a proper quality measure with a focus on instances that evolve worse than 'smoothly' - but on the other hand not in a worst-case manner. We propose two quality measures and apply these to the top-k monitoring problem and monitoring the count-distinct.

#### November 9, 2016, 2:00 pm, F1.110

Competitive Binary Tree Overlay Networks for Bandwidth-defined Streaming with Local Knowledge Only?

Overlay networks are a feasible way to abstract from physical layer networks, thus allowing restructuring the network with minimal effort. A binary search tree allows easy path finding between nodes and is therefore well suited as underlying structure of an overlay network. In my model pairs of nodes communicate continuously with a certain bandwidth demand. The goal is to find for the known bandwidth usage between nodes a tree that minimizes the cost incorporated by distance between pairs of nodes and their bandwidth usage. I propose a simple online greedy algorithm that uses constant local knowledge only. For the case of a simple communication pattern, i.e. every node x only communicates with nodes x-1 and x+1, I show that the algorithm is constant competitive to an offline optimal algorithm w.r.t. the cost of the final tree.

#### November 9, 2016, 2:30 pm, F1.110

Automatic derivation of paths from transport systems out of the 3D polygon model

In CAD-supported development of technical systems (machines, equipment, etc.) virtual prototypes are looked in its entirety in the context of virtual design reviews using a VR system, in order to early detect errors and need for improvements. One important part of the analysis is the analysis of transport routes for the material transport via conveyor belts or chains, or rail-based transport systems. These transport routes are animated in a VR system. One problem is that the information about the transport routes are usually not modeled in the CAD data or get lost during conversion between the CAD system and the VR system and the animation paths have to be manually recreated. In this talk I present an algorithm for the automatic detection of such animation paths from the raw polygonal 3D data of a CAD based transport system.

#### October 26, 2016, 2:00 pm, F1.110

A new proof of Seymour's 6-flow theorem

A nowhere-zero $k$-flow on a graph $G$ is an assignment of a direction of edges of $G$ and a valuation of the directed edges by integers from $\{\pm 1, \ldots, \pm (k-1)\}$ in such a way that in every vertex of $G$ the sum of incoming values equals the sum of outgoing ones. It is conjectured by Tutte that every bridgeless graph admits a nowhere-zero 5-flow. The best general approach to this conjecture is a result of Seymour stating that every bridgeless graph admits a nowhere-zero 6-flow. In this talk we provide a different proof of Seymour's result.
This is a joint work with Matt DeVos and Robert Šámal.

(Joint Research Seminar: Algorithms and Complexity & Discrete Mathematics, Research Groups Friedhelm Meyer auf der Heide, Kai-Uwe Schmid, Eckhard Steffen)

#### October 26, 2016, 3:00 pm, F1.110

Structural optimization of a 2D truss structure using Finite Element Models

Florarobotica is a European project focusing on bio-hybrid system of natural and artificial plants. The artificial plants consist of several robots that serve as a scaffold to support the plant. The robots have limited mechanical and computational power and the control mechanism of the system is distributed among the swarm of robots. Assembling process in Florarobotica is performed by human agents that are involved in the growth process. However, the robots decide themselves where and how to add another robots and perform the assembling process in a distributed way. Therefore, a collective decision is required to develop the structure. Some important questions in this regard include as: the level of stability of the structure built out of the robots; the level of exterior force that the structure can tolerate; and the methods which can be applied to optimize the structure towards higher stability.
In order to consider the mechanical behavior of the structure, the scaffold was modeled as a truss structure using finite element method (FEM). The mechanical stress and deformation of the structure under applied loading was investigated for the system under equilibrium conditions. The truss was modeled in two dimensional (2D) space consisting of rods and joints. The simplest collection of rods and joints that would build a construction to reach a specific point in a 2D space is a grid with point A as the left-bottom (root) and point B as the target in the right-top corners of the grid. Different patterns of 2D truss structures were analyzed by developing a FEM code. Finding mechanical stress and dis- placement of the rods, the weight of the structure was optimized by decreasing the weight of each rod without losing the mechanical stability of the system. Therefore, the rods under lower stresses were attributed by less area and the total weight of the structure decreased. Comparison between the initial weight of the structure and the final optimum design was indicated for different examples representing attractive results in decreasing the structure weight. In this work, the scaffold holding the plant is simulated by using a truss structure under applied loading and its weight is optimized using the proposed optimization technique is this work. The proposed method can be applied for the researchers/designers in different fields where the lightweight parameter is important such as gossamer structures, solar sails, lightweight buildings and also Florarobotica.

(Final Presentation Student research project (Studienarbeit))

#### October 19, 2016, 2:00 pm, F1.110

Towards Self-Organization and Adaptation in a Robot-Plant Bio-Hybrid System (Plant Binary Decision Wall)

In flora robotica, we investigate the possibilities of controlling the growth of natural plants by an autonomous, distributed robot system and the interaction between plants mediated by our robot system. Here we present the Plant Binary Decision Wall, where plant symbionts (climbing beans, Phaseolus vulgaris) grow along mechanical scaffold rods in between static robot symbionts. The distributed robotic nodes contribute to actuation by providing stimuli (light) to plant symbionts, detect plant presence, and communicate amongst each other as well as to human users. The first issue we would like to tackle here is the ability of the robots to automatically detect their topology and stay robust in case of replacing a robot or manually exchanging their positions. The second issue is the ability of the robots to adapt to the presence of an intruder light source (e.g., ambient light) and eliminate its effect by increasing/decreasing their light intensities.