# Wintersemester 2015/16

##### Marcus Nachtigall

#### March 15, 2016, 2:30 pm, F0.530

**Diffusion-limited aggregation on a simulated swarm of robots using BEECLUST algorithm**

The presented Bachelor-Thesis develops an algorithm for creating diffusion-limited aggregations in a simulated swarm of robots. The seed of this aggregation is the robot that is at the position with the highest light intensity as there is a light over the arena. The robots find this position with the BEECLUST algorithm and choose the seed-robot through leader election. To break other aggregations some robots leave as recruiters to advise the other robots of their knowledge. With this recruiters it is the goal that there is only one aggregation at the end. The executed experiments show that the algorithm works very well even if there are some changes in the environment.

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

##### Björn Feldkord

#### February 10, 2016, 2:00 pm, F1.110

**Online Resource Allocation in Competitive Environments**

We extend well known problems of resource allocation to models which incorporate features of the competitive analysis of online algorithms and algorithmic game theory. We give first results for a simple extension of the classical Ski-Rental Problem and will discuss step-wise extensions towards a complex resource allocation model. An approach to formalize online strategies in the discussed settings will also be presented.

##### Matthias Feldotto

#### February 3, 2016, 2:00 pm, F1.110

**Towards Approximate Nash Equilibria in Cost Sharing Games**

In this talk, we discuss our first steps towards the computation of apprimate equilibria in cost sharing games. We consider weighted congestion games with polynomial cost functions for the resources. Compared to standard (weighted) congestion games, the cost functions are only given for the whole resource, but not for each player. A cost sharing method is then used to determine the costs of each player. Next to the trivial proportional cost sharing where each player has to pay a share proportional to her weight, the Shapley cost sharing method is the most accepted one since each player has to pay her marginal contribution to the overall costs.

In this game setting, lots of research is going on. Especially, questions about the existence of equilbria and their quality are the topic of current research. We want to go one step further and look at approximate euqilibria and especially the computation of them. In this talk, we present the game setting, some of its properties and the first algorithmic ideas.

##### Pavel Podlipyan

#### February 3, 2016, 2:30 pm, F1.110

**On our way towards almost collisionless gathering of 4 robots**

In the following talk we are going to consider the gathering of the point like robots with limited viewing range on Euclidean plane in the continuous time model. We are going to consider modification of Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita. We will enhance the common unit disc graph model by the Gabriel graph. The enhanced strategy seems to gather the robots without collision from almost every configuration. Our talk is going to be mainly dedicated to the proof of this property for group of 4 robots and difficulties we confront with.

##### Daniel Jung

#### January 27, 2016, 2:00 pm, F1.110

**Local strategies for solving robot formation tasks**

We consider a swarm of n point shaped, autonomous robots on a grid. The robots do not have any global capabilities and can only move at most distance 1 in every round. Our time model is the fully synchronous FSYNC model. In the past, chain strategies have been used for shortening communication chains between two fixed endpoints. We have extended this to two even more challenging tasks where all robots are indistinguishable and execute the same (local) algorithm. The first result is gathering by shortening a _closed_ robot chain. Here, the robot's local vision and interaction additionally is restricted to only robots which are also local neighbors on the chain. Concerning other robots, even (weak) multiplicity detection is not possible. In our second result, we make the gathering task more common by dropping the given chain structure. The vision and interaction then remains local, but is extended to all robots within a constant radius on the grid. Here, one challenge is to find a general structure of the swarm that allows a fast progress in gathering. For the first model, we present a O(n)-time strategy. Under the second one, for certain swarm shapes, we can be even faster than this.

##### Maximilian Drees

#### January 27, 2016, 2:30 pm, F1.110

**Existence of Pure Nash Equilibria in Singleton & Matroid Bandwidth Allocation Games**

It is well-known that bandwidth allocation games generally do not possess pure Nash equilibria (NE). In this talk, we discuss how to restrict this class of games in order to obtain a guarantee for NE. The focus lies on singleton bandwidth allocation games, in which each player may locate himself on exactly one resource. If we restrict the number of resources or the number of different weights to 2, NE always exist. To some degree, these results can be extended to the matroid version of these games, as well.

##### Grammateia Kotsialou

###### University of Liverpool

#### January 20, 2016, 2:00 pm, F1.110

**Tight Bounds for Cost-Sharing in Weighted Congestion Games**

This work studies the price of anarchy and the price of stability of cost-sharing methods in weighted congestion games. We require that our cost-sharing method and our set of cost functions satisfy certain natural conditions and we present general tight price of anarchy bounds, which are robust and apply to general equilibrium concepts. We then turn to the price of stability and prove an upper bound for the Shapley value cost-sharing method, which holds for general sets of cost functions and which is tight in special cases of interest, such as bounded degree polynomials. Also for bounded degree polynomials, we close the paper with a somehow surprising result, showing that a slight deviation from the Shapley value has a huge impact on the price of stability. In fact, for this case, the price of stability becomes as bad as the price of anarchy.

##### Manuel Malatyali

#### January 13, 2016, 2:00 pm, F1.110

**On Competitive Algorithms for Approximations of Top-k-Position Monitoring of Distributed Streams**

Consider the continuous distributed monitoring model in which n distributed nodes, receiving individual data streams, are connected to a designated server. The server is asked to continuously monitor a function defined over the values observed across all streams while minimizing the communication. We study a variant in which the server is equipped with a broadcast channel and is supposed to keep track of an approximation of the set of nodes currently observing the k largest values.

Such an approximate set is exact except for some imprecision in an ε-neighborhood of the k-th largest value. This approximation of the Top-k-Position Monitoring Problem is of interest in cases where marginal changes (e.g. due to noise) in observed values can be ignored so that monitoring an approximation is sufficient and can reduce communication.

##### Sören Riechers

#### January 13, 2016, 2:30 pm, F1.110

**(1) Reducing traffic information for social welfare and (2) leasingmachines from the cloud**

My talk will cover two topics I am currently working on. In the first part, I will talk about selfish routing and how traffic information influences social welfare. If the traffic information provider can give any arbitrary information and the user always believes it is true, social welfare can be enforced to the optimum. However, we assume that the user knows about the probabilities that the provider does or does not give information. Here, examples where social welfare can be increased by omitting information with a certain probability are less obvious.

In the second part, I will talk about leasing machines from the cloud. In the parking permit problem introduced by Meyerson, leases have arbitrary capacities. This is not realistic in a model where machines are leased from the cloud. Instead, only one job can be finished at the same time. I will start with a very basic version of the model and introduce ideas how to solve the problems that occur when extending the model.

##### Mostafa Wahby

#### January 6, 2016, 2:00 pm, F1.110

**Controlled plant growth by exploiting the plant's phototropism**

We apply artificial evolution to a robot-plant bio-hybrid system to control the plant growth by exploiting the plant's phototropism. Control here means to grow the plant tip to certain positions while the controller switches lights on and off. The common bean plant (Phaseolus vulgaris), which is considered a fast grower, grows an average of 2cm to 3cm per day during the early growth stage. Hence, embodied evolution is not feasible. Therefore, we present our approach to create a simple beans growth-motion model from data obtained in plant experiments. Then, we use the model as a simulation to evolve closed-loop controllers. In addition, we show how well these evolved controllers work on real plants (reality gap).

##### Shouwei Li

#### January 6, 2016, 2:30 pm, F1.110

**MCVP with bounded genus k**

The Monotone Circuit Value Problem (MCVP) is s typical P-complete problem, which is unlikely to have a parallel algorithm for it. So we ask a new question, is that possible to fix a parameter of MCVP such that an algorithm with running time O(f(k)*log^c(n)) and O(n) processors could be obtained. In this talk, we consider the graph embedding as a fixed parameter k (genus), and involve a data structure called PQ-tree to represent planar subgraphs of the underlaying graph of the circuit. After decomposing the circuit into k different sub-circuits, we can evaluate the whole circuit in k steps.

##### Sascha Brandt

#### December 16, 2015, 2:00 pm, F1.110

**Towards on-the-fly rendering of emerging virtual worlds**

In modern computer graphics applications the requirement for rendering highly complex and dynamic 3-D content is becoming higher and higher. Furthermore, this content is often not known beforehand (e.g., in procedural generated scenes), such that traditional out-of-core algorithms are not feasible. In this talk I will talk about the challenges and possible solutions for generating and rendering three-dimensional approximations of highly dynamic scene geometry on-the-fly.

##### Mouns Almarrani

#### December 9, 2015, 2:00 pm, F1.110

**2-D shapes to increase the image quality in point-based rendering systems**

One of the big challenges in the 3-D computer graphics is the rendering of high complex scenes. To make the rendering of such scenes more efficient its complexity must be reduced. For this purpose approximation techniques are used. One of these techniques is point-based technique, that simplifies the complex geometry by replacing it by sample points.

In this thesis a new approximation process is developed, which is based on a point-based technique (Progressive-Blue-Surfels "PBS" by Claudius Jaehn). The main goal is to improve the image quality compare with the PBS with respect to the computaton's and rendering's time. The basic idea is to render 2-D shapes instead of points. In this way the problems in the image quality of the PBS like existing of hols, failing some details in the approximated surface and frayed contours could be solved.

(Introductory presentation Master’s thesis, talk in German)

##### Karsten Jungnitsch

#### December 9, 2015, 2:30 pm, F1.110

**Efficient Facade Grammar for Procedurally Generated Cities**

In the field of computer graphics, procedural generation describes algorithms that are used to generate content, such as buildings and plants. This represents an efficient alternative to creating all scenes and objects manually.

The higher level of abstraction allows the artists to create detailed and complex scenes with less effort. The goal of this thesis is to develop a new grammar system for the procedural generation of facades, based on CGA shape grammars, that is especially efficient for large scenes with hundreds of newly generated buildings.

One goal for this new grammar is to create buildings in multiple LOD levels. In addition, the grammar system has the task to shorten the generation time of building by introducing a data structure that is able to reuse already calculated parts of buildings.

(Final presentation Bachelor’s thesis)

##### Lennart Leder

#### December 2, 2015, 2:00 pm, F1.110

**Congestion Games with Mixed Objectives**

Congestion games are a useful tool to model situations in which selfish actors (called players) allocate shared resources. The players have to pay a price for each resource they are using and strive to minimize their cost, which is the sum of the costs of the resources they are allocating. As a variation of this model, in a Bottleneck Congestion Game the cost of the players is determined only by the most expensive of their resources. In my thesis I am going to examine so called Congestion Games with Mixed Objectives, which are a combination of these two game types.

(Introductory presentation Master’s thesis)

##### Syam Gullipalli

#### November 18, 2015, 2:00 pm, F1.110

**Decision Making in a Bio-hybrid Autonomous Robotic System (Cyborg Plant)**

The growth of plants can be supported and controlled by robotic assemblies through appropriate stimuli like light, touch, etc. Florarobotica is an EU funded research project, aims at investigating symbiotic relationship between robots and plants, and exploring the potentials of plant-robot hybrids to produce architectural artifacts. The focus of this master thesis is to implement a binary-decision wall with robotic nodes which are equipped with sensors and actuators to grow simple shapes out of plants, and to experiment on achieving consensus or disagreement between plants through robots. The results of this thesis will be testbeds for the research of florarobotica.

(Introductory presentation Master’s thesis)

##### Alexander Mäcker

#### November 18, 2015, 2:30 pm, F1.110

**Cost-efficient Scheduling on Machines from the Cloud**

We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs arriving over time. There are two types of machines available which can be rented for machine-type dependent prices and for any durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online, have machine-type dependent sizes and need to be finished before their respective deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since no online algorithm without or with a lookahead that is smaller than the setup times can be competitive, we consider algorithms that have some prior knowledge about the near future.

##### Michael Etscheid

###### University of Bonn

#### November 4, 2015, 2:00 pm, F1.110

**Bounds for the Convergence Time of Local Search in Scheduling Problems**

We study the convergence time of local search for a standard machine scheduling problem in which jobs are assigned to identical or related machines. Local search corresponds to the best response dynamics that arises when jobs selfishly try to minimize their costs. We assume that each machine runs a coordination mechanism that determines the order of execution of jobs assigned to it. We obtain various new polynomial and pseudo-polynomial bounds for the well-studied coordination mechanisms Makespan and Shortest-Job-First, using worst-case and smoothed analysis. We also introduce a natural coordination mechanism FIFO, which takes into account the order in which jobs arrive at a machine, and study both its impact on the convergence time and its price of anarchy.

This is joint work with Tobias Brunsch and Heiko Röglin.

##### Florian Pieper

#### October 28, 2015, 2:00 pm, F1.110

**Graph based real time global illumination for wide area scenes**

Global illumination is a key element to increase realism in virtual scenes. There are a lot of global illumination techniques, but most of them having the drawback of being very computational expensive. In praxis this means, that they can either only be applied to small scenes or do not guarantee real time frame rates.

In this thesis a new global illumination algorithm will be developed. The algorithm will base on a graph structure approximating the visibility relations within the scene. The light is distributed in the scene by using the graph's edges. To reduce the number of edges and in addition allow long distance edges, a voxel cone tracing approach will be used for calculating the visibilities. To cope with dynamic scene changes, unaffected parts of the graph should be reused, so that the time needed for calculating the visibility changes is reduced.

(Introductory presentation Master’s thesis, talk in German)

##### Jürgen König

#### October 21, 2015, 2:00 pm, F1.110

**Shared Resource Scheduling with Interconnected Services**

Consider a system in which different services are offered. Jobs composed of these services have to be processed. Communication between those services is necessary. The main performance limiting factors are the number of services active at a time and the required communication bandwidth between them. This master's thesis explores a new NP hard scheduling model for such a setting. The main goal is to derive approximation algorithms and prove their worst case runtime. In this talk an introduction into the topic will be given and the goals of the master's thesis will be presented.

(Introductory presentation Master’s thesis)