# Sommersemester 2013

#### September 30, 2013, 5:00 pm, F1.110

Local strategies for swarm robots with heterogenous sight ranges

Consider a set of simple robots moving in a two dimensional plane using a syn- chronous time model (LCM - Look, Compute, Move). The robots are oblivious and do no communicate. We investigate heterogenous robots in terms of their sight ranges to discover whether known local strategies can be improved with varying sight ranges. Investigations are focused on the Gathering problem - the task to gather all robots on an arbitrary point.

First the prerequisites for start configurations are analyzed. Using the results, two variants of the already known strategy GoToTheCenter are presented. Correctness and a runtime bound is shown for both variants. As a last part of this work, the strategy variants are evaluated by a simulator and compared to GoToTheCenter.

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

#### September 30, 2013, 5:30 pm, F1.110

Dispersion of Multi-Robot Teams

The robot gathering problem has been studied extensively in various variants. This master's thesis aims to do the opposite and to disperse the robots. Many applications require the robots to spread out, for example, in order to explore an unknown terrain or to monitor a large area with sensors. This thesis investigates the dispersion problem for a zig-zag line in which each robot knows its predecessor and successor. Initially, the robots are close together and they should form a straight line of maximal length while still maintaining connectivity. For doing so, we introduce a local, distributed algorithm, the so called Go-To-The-Middle strategy.

First, we investigate this strategy in one dimension where the robots are already placed on a (short) line. Let there be $n+1$ robots. We prove that the Go-To-The-Middle strategy needs time $O(n^2\log(1/\varepsilon))$ to reach a line of length at least $(1-\varepsilon)n$.

For the two dimensional case, in which the robots are placed in the two-dimensional plane, we prove that there are some placements of robots, called configurations, such that the Go-To-The-Middle strategy does not make the robots converge to a straight line of maximal length. However, we show that a large class of configurations do converge and prove their convergence. Furthermore, we consider a special case consisting of 4 robots and show that it takes time $O(\log(1/d)+\log(1/\varepsilon))$ to reach a line length of at least $(1-\varepsilon)n$ if the two outer robots had an initial distance of $d$.

Simulation results indicate that both the upper bound for one dimension as well as the upper bound for 4 robots are tight.

(Final presentation master's thesis, talk in English)

#### September 3, 2013, 3:00 pm, F1.110

Complexity and Approximation of the Continuous Network Design Problem

We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. We are given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed. The goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, even for instances with affine latencies.

As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Mathematical Programming, Vol. 34, 1986). Specifically, we derive a closed form expression of its approximation guarantee for arbitrary sets of allowed latency functions. Second, we propose a different approximation algorithm and show that it has the same approximation guarantee. As our final --  and arguably most interesting -- result regarding approximation, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we give a closed form expression. For affine latencies, e.g., this algorithm achieves a 49/41-approximation which improves on the 5/4 that has been shown before by Marcotte.

Joint work with Tobias Harks and Max Klimm.

#### August 16, 2013, 2:00 pm, F1.110

In-degree Bounded Network Creation Games

To understand the creation of the Internet and similar networks, we must understand the dynamics of networks produced by the interaction of many selfish agents. We attempt to acomplish this goal by studying a so-called Network Creation Game with selfish agents that buy links to each other in the network graph. Our In-degree Bounded NCG extends the NCG model introduced by Fabrikant et al. to consider the fact that agents cannot maintain an unlimited number of incoming connections. We study the Nash equilibria of this novel game and prove bounds for the Price of Anarchy and Price of Stability.

#### July 17, 2013, 2:00 pm, F1.110

On Two-Party Communication Through Dynamic Networks

The study of dynamics in networks has received great attention in the last years. Kuhn et al. model a dynamic network as an edge-dynamic graph that changes adversarially. Nodes in the network have unique IDs and each node may send one message of size O(log(n)) bits per round, where n is the number of nodes. A message sent by some node in round r is delivered to all its neighbors in the graph of the following round r+1.

In this talk, I would like to to present joint work on two-party communication in the context of directed dynamic networks that are controlled by a strong-adaptive adversary. This adversary is able to change all edges as long as the networks stay strongly-connected in each round. We were able to establish a relation between the problem of counting the total number of nodes and the problem of exchanging tokens between two predefined communication partners which communicate through a dynamic network.

#### July 5, 2013, 3:00 pm, F2.211

Greedy Network Creation With Heavy And Light Edges

Network creation games in different variants have been widely studied to model and analyze the emergence of networks of selfishly acting nodes. In these games it is often assumed that nodes can create undirected edges for the price of $\alpha>0$ which connect nodes with a distance of 1 and the nodes' objective is to minimize the cost for edges plus some distance cost in the resulting network. A question that has not been considered yet is to study what happens if nodes have the opportunity to choose between different edge types with different prices and weights. Therefore, in this thesis a new model will be analyzed: each node can choose between an edge for the price of $\alpha$ with weight 1 and one for the price of 1 with a weight of $\beta$, $\beta >=\alpha$.

To study the loss of quality due to the uncoordinated emergence, the quality of Nash equilibria in this model will be studied in a theoretical analysis as well as by simulations. Additionally, the approximation quality of Nash equilibria by greedy equilibria (Nash equilibria of specific polynomial-time bounded players) will be addressed.

(Introductory presentation of master's thesis)

#### June 26, 2013, 2:00 pm, F1.110

A Network Creation Game with Locality

Network creation games model the creation and usage costs of networks formed by a set of selfish peers. Each peer has the ability to change the network in a limited way, i.e., by creating or deleting incident links. In doing so, peers aim to reduce their individual communication costs, usually exactly computed with global knowledge about the network. We relax this global knowledge assumption and introduce a strict locality of the peers: A peer is only aware of other peers in its direct 2-hop neighborhood. To estimate their private costs (given by a weighted sum of shortest path distances to all other peers in the network), peers must make assumptions about the positions of other peers in the network. For our model we present bounds for diameter, convergence time, and loss of efficiency by the selfish behavior. Furthermore, we use our analysis results to design a self-stabilizing protocol that creates a robust small-world network among the peers, providing a logarithmic diameter of the network.

#### June 26, 2013, 3:00 pm, FU.116

Rendering and Interaction Techniques for Virtual Design Reviews

Virtual Design Reviews can be a powerful tool to support design decisions and to identify problems in the development process of intelligent technical systems. The complexity of such a technical system can induce challenges in different areas:
For the preparation of the design review session, the system’s CAD data has to be processed and enriched with animations to allow a realistic presentation of the appearance and behavior of the virtual prototype. By developing new tools for a direct interaction with the virtual prototype, we try to greatly reduce the necessary effort for this step. Another challenge is the complexity of the virtual 3d scene, created from the CAD data, which has to be rendered at interactive frame rates for the design review session.
In this talk, I’m going to present current and planned interaction tools and rendering algorithms implemented in the PADrend-system, in the context of the Leading Edge Cluster project CQP-MMI.

#### June 19, 2013, 2:00 pm, F1.110

Local gathering algorithms and mobile robot coordination problems

Gathering of mobile robots in one not predefined point on the plain is one of the basic and widely studied coordination problems. We consider robots with limited viewing range that act in continuous model of the environment and present current runtime analysis results of minimum enclosing circle algorithm in given model. Besides that second half of the talk will be dedicated to open questions in mobile robot coordination.

#### June 12, 2013, 2:00 pm, F1.110

Approximative Rendering using Sample-Based Occlusion Culling

In this talk I will present the results of my master's thesis in which I developed a new approximative rendering algorithm for complex 3-d scenes. This new algorithm is based on the Spherical Visibility Sampling and the Blue Surfels algorithm. In a preprocessing step it detects visible triangles of a part of the scene and stores them in a list. These will be arranged within this list in such a way that every prefix is a good representation of this part of the scene. When rendering a preprocessed scene the user can set the triangle budget, the maximum number of rendered triangles, to an arbitrary value. The renderer will then distribute the budget among the visible parts of the scene and display the prefix of according length. This way the new algorithm achieves real-time rendering of complex 3-d scenes while maintaining a high image quality. In the talk I will describe the algorithm in more detail and present results of the experimental evaluation.

(Final presentation master's thesis)

#### June 5, 2013, 2:00 pm, F1.110

Shared bandwidth scheduling

In modern compute centers, there are thousands of processors. These processors (or subsets of them) often share a common resource such as memory or data connection. Sometimes, this common resource can become the bottleneck of the whole system, especially if data throughput is high. In my talk I introduce a new model considering a multiprocessor environment with identical, fixed-speed processors sharing a common resource or bandwidth. The bandwidth is the bottleneck of the system, i. e. if a job has to be slowed down, this is due to the required bandwidth not provided in some time step (we consider the problem as a discrete model). Processing only parts of a job in one time step is allowed - this is the new aspect in comparison to previous models. I present basic strategies and ideas to solve the problem and future modifications that could be interesting.

#### May 29, 2013, 2:00 pm, F1.110

A Distributed Approximation Algorithm for Strongly Connected Dominating-Absorbent Sets in Asymmetric Wireless Ad-Hoc Networks

Dominating set based virtual backbones are used for routing in wireless ad-hoc networks. Such backbones receive and transmit messages from/to every node in the network. Existing distributed algorithms only consider undirected graphs, which model symmetric networks with uniform transmission ranges. We are particularly interested in the well-established disk graphs, which model asymmetric networks with non-uniform transmission ranges. The corresponding graph theoretic problem seeks a strongly connected dominating-absorbent set of minimum cardinality in a digraph. A subset of nodes in a digraph is a strongly connected dominating-absorbent set if the sub graph induced by these nodes is strongly connected and each node in the graph is either in the set or has both an in-neighbor and an out-neighbor in it. My talk presents our distributed approximation algorithm for this problem in disc graphs.

#### May 22, 2013, 2:00 pm, F1.110

Augmenting Your Analysis-Arsenal for Online Problems

Algorithms for online problems have to deal with the lack of knowledge about future events. While  sometimes it is possible to come up with online algorithms that are not too bad when compared to an optimal offline solution, more often than not the price one has to pay for not being clairvoyant is rather high. Resource augmentation formalizes the idea of compensating for the lack of knowledge by more speed, more memory, .... Typically one is interested to quantify in how far this more "something" can make up for the missing knowledge about the future.

In my talk I consider a relatively new kind of resource augmentation recently suggested by S. Albers and M. Hellwig. The basic idea is to allow online algorithms to generate more than one (but essentially independent) online solutions and to charge only for the best one. Depending on the problem at hand this can be seems as augmenting the system with more machines or more space, but this approach can also be applied to more general situations. I present some of the results by Albers and Hellwig to give an example of this approach. They consider the makespan minimization problem, one of the most fundamental optimization and scheduling problems. At the end, I give a short outline of problems that I think are promising candidates for this approach.

#### May 22, 2013, 2:30 pm, F1.110

Scheduling Variants with Speed-Scaling via the Primal-Dual Approach

In this talk I will present the final results of my master’s thesis. The focus of my work lies on energy-aware scheduling algorithms for speed-scalable systems. Such algorithms allow for significant energy savings and thus may help to reduce the operational costs of data centers or the battery life of mobile devices. My work had two main objectives. On the one hand, I evaluated a novel analysis technique: the so-called online primal-dual approach. This technique utilizes duality theory to derive suitable online algorithms. On the other hand, I investigated possible extensions of current models by the inclusion of interruption costs (e.g., job-preemption). In my talk I will give a brief overview on two of the problems I looked at. I will outline the problems that I encountered when applying the online primal-dual approach to models including interruption costs and I will present a new model for scheduling with speed-scaling and preemption costs. Most notably, I will present a constant-approximation algorithm for the offline setting of this new model.

(Final presentation master's thesis)

#### May 8, 2013, 2:00 pm, F1.110

Dispersion of Multi-Robot Teams

The robot gathering problem has been studied extensively in various variants. This master's thesis aims to do the opposite and disperse the robots. Many applications require the robots to spread out, for example, in order explore an unknown terrain or to cover a large area with sensors. The first step towards this goal will be to place the robots close together on a one dimensional line and to develop and analyze algorithms to distribute the robots uniformly in a fixed distance. The second step will be to do the same in two dimensions: initially, the robots are close together in the two dimensional plane and they should form a straight line with a fixed distance between them. Interesting properties that might be studied via simulation and theoretical analysis are whether the robots actually converge to a straight line and how long it takes. The last step will be to generalize the algorithms and analysis techniques. One idea might be to reverse the gathering algorithm, i.e., maximize the minimal distance between robots, and see if it is suited for the dispersion problem.

(Introductory presentation of master's thesis, talk in English)

#### April 24, 2013, 2:00 pm, F1.110

The circular chromatic index of $k$-regular graphs

The circular chromatic index of a graph $G$ is the infimum of all rational numbers $p/q$, such that there exists a circular $p/q$-edge-coloring of the graph $G$. It is an interesting problem to determine the set of possible values of the circular chromatic index of $k$-regular graphs.

In this work we construct $k$-regular graphs with certain circular chromatic indices of the form $k+a/p$, in particular graphs for all $a \in \{1,2,\ldots,\lfloor k/2 \rfloor\}$ and $p\ge 2a^2+a+1$.

#### April 17, 2013, 2:00 pm, F1.110

Algorithms for 3D Rendering using Cloud Computing

Modern technology led to tablets and smartphones as more portable versions of workstations and even laptops. However, storage and computational power is still limited. Rendering complex 3D scenes is a challenging problem on these devices when using conventional methods. Our project group addressed highly complex scenes, by creating a remote rendering system, providing mobile devices with support from a cloud.
We developed a hybrid rendering algorithm for low performance devices, which uses point-based and standard polygon rendering simultaneously. An additional mechanism tries to automatically modify the renderer's parameters, depending on the available processing power. To complement the rendering system, we implemented the client and server side of a network service, providing different functionalities to support the mobile device.

(Final Report)

#### April 10, 2013, 2:00 pm, F1.110

Roboterschwarmbewegungen auf einem Gitter

A Crowd of fishes is a swarm. Although there are thousands of individuals, they act and move like one global unit. Each fish can only see and therefore influence a small part of the swarm. If there is one fish leading the swarm, then the question is how do the others get to know the direction to move?
We adapt this problem for swarm theory and consider a swarm of indistinguishable robots on a two dimensional grid. One robot is assigned as a leader, and has additional knowledge of a fixed path. The leader moves on this route, and the other robots shall follow him, without losing connection of the swarm. In this master thesis we will get to know the problem, and take a look at first ideas for moving strategies. Thus we want our robots to use only local information, we will see what difficul-ties may arise.

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