Winter Term 2016/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) leasing
machines 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)