# Sommersemester 2014

#### September 2, 2014, 2:00 pm, F1.110

Gathering of autonomous mobile robots with incomplete vision

The gathering of autonomous mobile robots has been the focus of a lot of research in the past. However a very general model has never been analyzed: incomplete vision. We want to introduce a global adversary that has the power to delete points from the snapshots of the robots. Changes to the restrictions on the adversary and the capabilities of the robots will lead to different configurations of the model. Models like the „limited visibility“ can easily be simulated with this adversary. The master’s thesis will focus on the most interesting configurations of the model and the goal is to show if gathering is possible and how fast.
The first model configuration, which will be the main focus of this talk, will give the adversary a lot of power. It can delete the complete snapshot of a robot as long as each pair of robots will see each other indefinitely often. Additionally the adversary can disconnect the visibility graph. Depending on the activation schedule and symmetry it is possible for the robots to gather or not. Other configurations like the „fog plane“ and a randomized adversary will also be introduced.

(Introductory presentation master’s thesis)

#### September 2, 2014, 2:30 pm, F1.110

An Out-of-Core-Algorithm for Rendering of Large Dynamic Scenes

The efficient rendering and navigation of very large, complex, three-dimensional scenes is a well known problem in computer graphics. It finds applications in many areas, such as architecture, CAD, or computer games. The challenge is to efficiently render 3d data, which does not fit into the memory of modern computers, such that the image quality is sufficiently good. Furthermore, it might be a requirement, that the 3d scene has to be altered during runtime, e.g. for design- and review-processes. This thesis focuses on the development of such an out-of-core rendering algorithm, which can efficiently render very large complex scenes in realtime and handle dynamic changes of the scene at runtime.

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

#### July 16, 2014, 2:00 pm, F1.110

On variants of the page migration problem

In the original page migration problem, a memory page is located on one processor in a network. The other processors can send requests to the processor holding the page indicating that they want to have access to data located within the page. These requests must be served and induce costs proportional to the distance between the requesting processor and the page. After every request, the page can be moved to another location, inducing costs proportional to the distance between the current and the target location of the page and proportional to the size of the page.
We divide time into slots. In each time slot, only one request can be made to access the page. We want to investigate whether methods applied to the original problem can be extended to allow multiple requests in a time slot and how their competitive ratio changes. We also try to derive new methods for this model.
In another approach, we want to fix the location of the page but allow the network structure to be changed; for example we allow the buying of new edges for fixed costs or the renting of edges over a certain time span.

(Introductory presentation master's thesis)

#### July 9, 2014, 2:00 pm, F1.110

Gathering a closed chain of simple agents in the grid

Assume we have a crowd of indistinguishable, point-shaped mobile agents, distributed on the plane. Each of these agents is connected to exactly two neighboring agents this way, that they form a closed chain (self intersections are allowed). The agents do not have any global knowledge, especially just a constant viewing range. At the moment, for easier analysis, we allow some limited features like counting rounds and limited communication, which might both possibly be removed in the future. In my model, i restrict possible positions of the agents to Z^2. I'm currently developing an algorithm that can gather this given chain withing a linear number of timesteps.

#### July 9, 2014, 2:30 pm, F1.110

Gathering almost without collisions

In the following presentation 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 introduce modification of well-known Go-To-The-Center strategy due to Ando, Suzuki, and Yamashita. We show that this modification still correctly executes gathering in time $O(n^2 )$, but has severe impact on the behavior of the strategy: no collisions appear for almost every initial configuration, except for the final step, when all robots simultaneously meet in one point.

#### July 2, 2014, 2:00 pm, F1.110

Randomized Online Algorithms for Set Cover Leasing Problems

In the leasing variant of Set Cover presented by Anthony et al., elements U arrive over time and must be covered by sets from a family F of subsets of U. Each set can be leased for K different periods of time. Let |U| = n and |F| = m. Leasing a set S for a period k incurs a cost c^k_S and allows S to cover its elements for the next l_k time steps. The objective is to minimize the total cost of the sets leased, such that elements arriving at any time t are covered by sets which contain them and are leased during time t. Anthony et al. gave an optimal O(log n)- approximation for the problem in the offline setting, unless P = NP. In this talk, I present our recent results which give randomized algorithms for variants of Set Cover Leasing in the online setting, including a generalization of Online Set Cover with Repetitions presented by Alon et al., where elements appear multiple times and must be covered by a different set at each arrival. Our results improve the O(log^2(mn)) competitive factor of Online Set Cover with Repetitions  to O(log m log(nd)) = O(log m log(mn)), where d is the maximum number of sets an element belongs to.

#### July 2, 2014, 2:30 pm, F1.110

Analyzing Complex Infinitely Repeated Games with Methods from Evolutionary Game Theory

In this talk we will present an approach to analyze complex infinitely repeated games with methods from evolutionary game theory. Therefore, we use techniques from both fields, repeated/stochastic games and evolutionary game theory, together with simulations. Especially for the analysis of global markets with thousands of participants and complex strategic behavior where the impact of a participant's strategy is not directly traceable we need new techniques to gain insights on the development and dependencies of the different market participants. These new understandings helps us in the design of good market conditions and environments. We work on new complexity and dependency statements in the intersection between the field of stochastic games on the one side and evolutionary game theory on the other side. In the talk we give an overview on current results and the on-going work in this topic. We present first results from simulations and give an outlook on planned empirical and theoretical research in this wide area.

#### May 28, 2014, 2:00 pm, F1.110

A new Theoretical Model for Multiprocessor Environments

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. I will introduce a theoretical model within a multiprocessor environment with identical, fixed-speed processors sharing a common resource or bandwidth. Moreover, we add precedence constraints. For this first model, we assume these precedence constraints to be linear, that is every job has at most one predecessor and one successor. The assignment of the services to the processors is fixed, i. e. there is one queue of jobs on every processor and they have to be finished in that order. 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 theoretical models. I present basic strategies and ideas to solve the problem and future modifications that could be interesting.

#### May 28, 2014, 2:30 pm, F1.110

Multilevel Network Games

We consider a multilevel network game where nodes of a slow general purpose network can improve their communication costs by connecting to a high-speed network. The general purpose network is a static network and each node can decide individually to become a gateway node or not. The goal of a node v is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from v to all other nodes plus a fixed price \alpha > 0, if it decides to be a gateway. Between gateways the communication distance is 0, and gateways also improve other nodes' distances by behaving as shortcuts. For the SUM-game with n nodes, we show that for \alpha < n-1, the price of anarchy is \Theta(n/\sqrt{\alpha}) and in this range equilibria always exist. For the MAX-game, we show that the price of anarchy is either \Theta(1 + n/\sqrt{\alpha}), for \alpha >= 1, or else 1. Given a graph with girth of at least 4\alpha, equilibria always exist in the MAX-game. Concerning the dynamics, both the SUM-game and the MAX-game are no finite improvement property games. For the SUM-game, we even show that it is not weakly acyclic.

#### May 21, 2014, 2:00 pm, F1.110

About network properties influencing the efficiency of replication in peer-to-peer networks

Replication in peer-to-peer networks can be used not only to increase robustness, but also for shortening routing paths. A bunch papers provide replication algorithms either for general graphs or for specific structured graphs. Here, an interesting question arises: Can we characterize graph properties that characterize how well replication in a certain structured graph performs? In this talk, it will be discussed whether such properties exist and what insights they provide about how the structure of an overlay should look like.

#### May 21, 2014, 2:30 pm, F1.110

Understanding the language of Big Data in distributed Environments

Consider a distributed Environment with n Sites and one Coordinator. The Sites can communicate to the server, but not to each other. The n Sites get Data Streams, one Data Stream for one Site, and the Coordinator should compute a function based on the union of all Streams. The goal is to minimize the communication, in order to let coordinator output the correct value of the function. In the Turnstile Model the Data Stream can consist of incoming events 1, and also leaving events -1. In the class of Monitoring algorithms the coordinator generates an output in each round. In a more restrictive model, which is called Cash Register Model and doesn’t allow leaving events, there are several problems well understood, e.g. the Countdown-Problem in which the coordinator outputs 1, if a given Threshold exceeds. We extend the model by a new approach of so called grammar based data streams. This technique allows to see coherences between structure of the generated Data Stream and needed communication. In the second part of the talk we consider position based queries in which a querying node is interested in local information in his neighborhood. In order to reduce the given information in the surrounding we extend a well-known technique of coresets to so called mergeable coresets.

#### May 14, 2014, 2:00 pm, F1.110

Budget-restricted utility games with ordered strategic decisions

We introduce the concept of budget games. Players choose a set of tasks and each task has a certain demand on every resource in the game. Each resource has a budget. If the budget is not enough to satisfy the sum of all demands, it has to be shared between the tasks. Otherwise, every task receives its full demand. This defines a utility for each task, which is the sum of these shares. Each player tries to maximize its own sum of utilities. We briefly mention strategic budget games, where the budget is shared proportionally. We then focus on a variant called ordered budget
games, in which the order of the strategic decisions influences the distribution of the budgets. Starting the game in an arbitrary state, players perform strategy changes by choosing new tasks and dismissing old ones. For a new task, the share which is satisfied of each demand is at most the remaining budget of the resource. The talk covers the complexity of optimal solutions and equilibria as well as the price of anarchy for ordered budget games.

#### May 14, 2014, 2:30 pm, F1.110

Realtime Global Illumination for big and dynamic scenes

Global Illumination is a huge advantage in virtual environments to enhance the realism of the scene. The big disadvantage is its high computational efford and memory usage, that comes with most algorithms, which approximate the Global Illumination. Some earlier works already have shown, that with today's hardware it is just now possible to deal with this challenges in realtime. Achieving this some special algorithms fitting to the graphics hardware must be developed. In my masterthesis a new approach to solve this challenge will be developed, which is based on a graph. This graph is passed to the graphics hardware and will make it possible to reuse the visibility checks. The thematic priority of this work is to allow interaction with the program, while using this solution to render a big scene with multiple dynamic objects and lights.

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

#### April 30, 2014, 2:00 pm, F1.110

Dynamic Networks meet Big Data

We consider extremum, summation, and dissemination problems in a dynamic network that is controlled by an adaptive adversary. Combining aggregation techniques with information dissemination algorithms, we show that extremum problems can be solved faster than summation problems which again can be solved faster than dissemination problems in a special class of dynamic networks. In addition, we also study continuous versions of these problems where the nodes of the network are given new inputs in each round. Here, the nodes have to compute a function of all values from same round and output as many results for different rounds as possible. We are able to show that by applying a pipelining technique we can increase the output rate of the algorithms.

#### April 30, 2014, 2:30 pm, F1.110

Efficient Creation of Interactive 3D Scenes 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. 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. In this talk, I’m going to give an overview over several techniques, developed in the context of the Leading Edge Cluster project CQP-MMI, aimed at reducing the necessary overhead for preparing a virtual prototype.

#### April 16, 2014, 2:00 pm, F1.110

P2P-based infrastructure for OTF-markets

This talk introduces the problems that are faced by the Project Group "DynaSearch - P2P-based infrastructure for OTF-markets" within the SFB 901 "On-The-Fly Computing". We give an overview of our past, current and future work, which splits into two areas. On the one hand, we look at Network Creation Games where nodes in a network selfishly adapt the network to their interests. In particular, we consider the case that the interests of each node change over time and analyse if the whole network reaches a stable state. On the other hand, we examine two multidimensional search problems in a distributed setting and mainly look for efficient algorithms. The first one is classical range query whereas the second search asks for an item that maximizes or minimizes a given objective function.

(mid-term presentation project group)