Winter Term 2014/15

Till Hohenberger

March 25, 2015, 2:00 pm, F1.110

Network Creation Games with Interest Groups

We introduce Network Creation Games with Interest Groups (IGNCGs) as a variant of classical Network Creation Games. In IGNCGs n players are assigned to k groups, such that every player is assigned to one group. Players create or delete connections to other players with the goal to be (indirectly) connected to all groups. Each player selfishly minimizes a private cost function, depending on the number of created edges plus its distances to all groups. In SUM-IGNCGs the players’ cost functions depend on the sum of the distances to all groups, whereas in MAX-IGNCGs the maximal distance to one group is taken into account.
We focus on Nash Equilibria, i.e., states in which none of the players can decrease their costs by creating or deleting connections. We present bounds for the factor between the cost of a worst case equilibrium and the optimal solution for all players, the so called Price of Anarchy in SUM- and MAX-IGNCGs.
Furthermore, we prove that infinite sequences of connection changes exist, i.e., players may never reach an equilibrium. In our simulations, despite their theoretical possibility, we never encountered such infinite sequences, but observed that players in IGNCGs reach a Nash Equilibrium after a linear number of connection changes. Lastly, we analyze the influence of changing players’ groups to the diameter of some worst case Nash Equilibria. 

(Final presentation Master’s thesis)

Tobias Rojahn

March 25, 2015, 2:30 pm, F1.110

Load Balancing for Range-Queries in a Dimension Invariant Peer-to-Peer Network

Support of range queries has become a common requirement for peer-to-peer systems, e.g., for the dynamic composition of services to a software. Markus Benter developed a constant-degree dimension invariant range query system on a theoretical model. It utilizes the Hilbert Curve and a binary tree for efficient routing to achieve optimal response time and bounded message complexity. My thesis adapts this concept to real world network conditions. I provide local algorithms for building the desired structure in a peer-to-peer system. Further I present a technique for dealing with load imbalance in the hierarchical tree routing structure. Simulation with PeerfactSim.KOM is used to evaluate the system.

(Final presentation Master’s thesis)

Matthias Feldotto

March 4, 2015, 2:00 pm, F1.110

Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria

In this talk we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions.
We show that the value of the potential function of any outcome of a congestion game approximates the optimum potential value by a factor Ψ(F) which only depends on the set of cost/utility functions F, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome.
The significance of this result is twofold. On the one hand it provides Price-of-Anarchy-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute (1+ε)·Ψ(F)-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.

Christine Markarian

March 4, 2015, 2:30 pm, F1.110

A new framework for online leasing problems

Typical infrastructure problems consider scenarios where one has to buy certain goods or resources in order to generate or improve a given infrastructure. Such problems have not only been widely studied in the offline- but also in the online-setting, where the decision of which goods to buy and when must be taken when demands are revealed, without the knowledge of future demands. Recently, Meyerson [FOCS 05] introduced the leasing setting in which resources can be purchased/leased for various periods of time (day, week, month) with different costs. The standard assumption in all these settings is that once a demand is revealed, it needs to be fulfilled on the spot. In this talk, I present a new framework for leasing problems where demands need not be fulfilled at the time of their arrival but may be postponed up to some fixed period of time (deadline). This captures many real-world scenarios where although we may not know future demands, we may still be informed of demands sometime a prior i and have freedom to decide when to fulfill the demands any time before their deadline.

Daniel Jung

March 4, 2015, 3:00 pm, F1.110

Gathering of point-shaped Robots

Assume a crowd of n point-shaped robots. These robots shall only have a local view, no global knowledge about the scenery and can only perform local modifications to it. Initially, the robots are arbitrarily distributed under the contraint that the visibility graph needs to be connected. All robots act simultaneously, i.e., we are in the FSYNC time model. In this setting, we currently can not gather faster than in time \Omega(n^2). In the talk, we present approaches, starting with worst case instances for known strategies, how gathering could be solved in sublinear time.

Pavel Podlipyan

March 4, 2015, 3:30 pm, F1.110

Almost everywhere collisionless gathering of 4 robots

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 consider modification of Go-To-The-Center algorithm due to Ando, Suzuki, and Yamashita.
We show that set of initial configurations of 4 robots that leads to collision during runtime of our modified algorithm is Lebesgue measure zero set. The end of the talk will be dedicated to general case with $n$ robots and the problem that is needed to be solved in order to prove collisionless property in this case.

Jannis Pautz

February 4, 2015, 2:00 pm, F1.110

Budget Games with priced strategies

In this thesis, the model of budget games with prices is introduced. It is based on budget games, where players demand resources with a limited budget. A player chooses a set of tasks and each task expresses demand on certain resources. If the the sum of all demands for a resource exceeds its budget, the budget has to be shared between the tasks. Those budget games are extended by prices for tasks and therefore also strategies. Using a new developed simulator for the budget games with prices, they are examined regarding the existence of Nash Equilibria, the weak speed of convergence and the prices of anarchy and stability. Finally, it is shown that the price of anarchy, as well as the price of stability, is unbounded. Furthermore, it is observed that the weak speed of convergence is always finite.

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

Maria Gerges

February 4, 2015, 2:30 pm, F1.110

Automated determination of geometrical properties of polygonal 3D objects

An important phase during an engine development process is the virtual design review. Here, concepts and designs of a product are being systematically assessed, so that errors and demands of improvements can be detected early. Also through the visualization of the product there is no need of real prototypes in order to examine the process operation. However, through the conversion of CAD models into polygonal 3D models, important geometric information gets partially or completely lost. So far, the determination of such information is done manually.
The aim of this thesis is to speed up this process by automating the calculation for one of those geometrical properties, namely, the rotational axes of cylindrical objects. The developed algorithm is then evaluated using different objects.

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

Markus Benter

February 4, 2015, 3:00 pm, F1.110

Dimension Independent Peer-to-Peer Systems for Query Processing on Multi-Dimensional Objects

First, we  introduce the definition of "Dimension Independent Networks". This property allows Peer-to-Peer system to deal with multi-dimensional objects where the dimensionality of the objects change during runtime and/or cannot even be predicted before the actual system is deployed. We argue that this property is desirable in practice. In the following, we focus on multi-attribute range queries where objects are d-dimensional vectors with entries of the [0,1] interval. The state of the art Peer-to-Peer systems being able to solve such queries are discussed having a special focus dimension interdependency. Thereby, we carve out open research questions concerning dimension independent Peer-to-Peer systems for multi-attribute range queries.

Christian Stromberg

January 23, 2015, 2:00 pm, F0.530

Global Illumination in Screen Space with Additional Cameras

Real global illumination in rendering is time-consuming due to the complexity of the calculation. Hence approximations are needed to calculate global illumination in real-time. One popular approximation is Screen Space Ambient Occlusion (SSAO) which approximates the calculation of lighting by using the frame-buffer as approximation of the scene.
This thesis extends a SSAO-based method by calculating positions for additional cameras to gain more information about the scene, which should let the resulting image appear more real. For this purpose, two different position calculations for the additional cameras are compared to the method without additional cameras. These extensions are evaluated in terms of the performance and the quality of the resulting image.

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

Peter Stilow

January 23, 2015, 2:30 pm, F0.530

Realtime Global Illumination for big and dynamic scenes

Global Illumination gives many visual benefits to the appearance of a rendered virtual scene. Although there is much research done in this field to enhance the illustration further, the complexity of it's calculation remains a very time consuming task. Global Illumination is often exchanged by some precomputations or it is replaced by some techniques are used, which strongly approximate the results. Therefore it is barely possible to achieve a speed of calculation, so that an interaction with the program would still be possible. In this work a new method is introduced, which calculates the Global Illumination for a big and dynamic szene. This method uses a graph, which is created inside the complete virtual szene. The graph is used to approximate the Global Illumination by pushing the intensities of all light sources along the edges further into the scene to other objects. In the next step, the surfaces are illuminated by the near nodes of the graph. To gain an interactable program, where the calculation of the Global Illumination is done at runtime, the algorithm heavily depends on the graphics hardware. In order to show the performance of this algorithm, some tests are made with a szene which consists of about two million polygons.

(Talk in German, Final presentation Master’s thesis)

Andreas Cord-Landwehr

January 7, 2015, 2:00 pm, F1.110

Self-Adapting Overlays by Selfish Peers

Network Creation Games (NCGs) are a game theoretic model to capture the outcomes of networks created by selfish peers. We assume these peers to perform myopic changes to the network (creating, removing, or swapping edges) in order to optimize their own costs. The costs of a peer consist of the money spent for creating edges plus the communication costs, for communicating with all other peers.
This talk consists of two parts: In the first part, I will present (in a condensed form) our results on the track to approach application dynamics in the NCG framework. The second part is about our current work in this field in studying game variants incorporating effects of multilevel networks and network locality.

Tobias Rojahn

December 17, 2014, 2:00 pm, F1.110

Load Balancing for Range-Queries in a Dimension Invariant Peer-to-Peer Network

Support of range queries has become a common requirement for peer-to-peer systems, e.g., for the dynamic composition of services to a software. Such systems have additional requirement for load balancing compared to basic distributed hash tables. Simple redistribution of nodes in the peer-to-peer structure can not achieve load balance, when load is not tied to data-items but sections of key space. My thesis will address those issues for the dimension invariant peer-to-peer network developed by Markus Benter. The solutions will be evaluated experimentally using simulation.

(Introductory presentation master’s thesis)

Hendrik Hilleckes

December 17, 2014, 2:30 pm, F1.110

Gathering of autonomous mobile robots with incomplete vision

The gathering at a single point is a widely studied problem in the field of autonomous mobile robots. The task is well understood and the capabilities needed were shown. However there was always one assumption on the environment of the robots: either they have a complete view of the system (e.g. they see every other robot) or a very specific vision impairment was defined. One example would be a vision range or limited visibility. With this impairment the robots could only observe other robots inside a given vision range. In this thesis an adversary will be introduced that can delete robots freely from the snapshots of other robots. This means that this adversary can simulate every other vision impairment. This thesis shows that gathering is in fact impossible if the adversary is too powerful. But convergence, a closely related task, can be achieved. This is shown for the algorithm GoToIntervalCenter, a new algorithm introduced in the thesis. This algorithm manages to converge the robots even if the adversary is allowed to disconnect the visibility graph. The only restriction is that each pair of robots needs to see each other infinitely often. The algorithm GoToThe- Center was analyzed in the same environment. A collection of useful insights of the behavior of this algorithm will be presented together with a sketch for a convergence proof that relies only on a single reasonable assumption. This thesis also contains the results of simulations of three algorithms that try to converge while a randomized adversary deletes robots from the snapshots. The results show that the fastest and most stable algorithm in this model is GoTo- CenterOfGravity, an algorithm that lets the robots move to the center of gravity of all the robots it sees. The performance of GoToTheCenter on the other hand is influenced greatly be the initial configuration of the robots.

(Final presentation master’s thesis)

Sören Riechers

December 10, 2014, 2:00 pm, F1.110

Analyzing speed scaling with an upper speed limit by extending the KKT conditions

In my talk, I consider a speed scaling problem with upper speed limits and where energy prices change over time. Here, I propose a new analysis framework for continuous problems where the discrete version can be solved by means of the KKT conditions. More exactly, I use variational calculus known from mathematics in order to use functions as variables (namely functionals) instead of usual, discrete variables. Doing so, results from optimization using the known KKT conditions carry over to this continuous version of the problem and we can develop an extended version of the KKT conditions. This is especially interesting insofar as we hope that these extended KKT conditions can also be applied for different kinds of problems.
During my talk, I will present the idea of our algorithm that solves the specified speed scaling problem optimally and what it looks like for both versions of the problem. For the discrete case, where the upper speed limit and the energy prices need to be piecewise constant, the optimality can be proved by using the sufficiency of the KKT conditions for optimal solutions. However, the optimality of the algorithm for the continuous case can only be shown by using the extended KKT conditions and the corresponding KKT theorem developed before.

Markus Benter

November 26, 2014, 2:00 pm, F1.110

A Dimension Invariant Constant Degree Peer-to-Peer System for Multi-Attribute Range Queries

Peer-to-Peer networks allow to build up decentralized search infrastructures that are able to make centralized server solutions obsolete. We consider quite complex data items (objects), i.e., vectors of the form [0,1]^k. As queries, we study range queries, i.e., a query is defined by an individual upper and lower bound for each of the k attributes of an object.
This talk is about the current development of a Peer-to-Peer system that, for the first time, fulfills the following three properties:

  1. It provides a constant degree peer-to-peer overlay
  2. It has an asymptotically optimal response time of O(log n)
  3. It has a non-trival bound on the message complexity in dependence on the requested range

I addition to that, a key feature of the system is that k may vary even during runtime of the system without any restructuring overhead. This means that our Peer-to-Peer System is dimension independent with respect to the dimensions of the data objects that are actually stored.

Manuel Malatyali

November 26, 2014, 2:30 pm, F1.110

Online Top-k-Position Monitoring of Distributed Data Streams

Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log ? + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where ? is upper bounded by the largest value observed by any node.

Till Hohenberger

November 19, 2014, 2:00 pm, F1.110

Network Creation Games with Interest Groups

In classic Network Creation Games, n players aim to (indirectly) connect to each other. Each player selfishly minimizes its private cost function (i.e. only considers its own cost). Therefore, players can create edges to other players or delete the edges they created. Each edge can be used by both players connected to it. The cost for each player is proportional to the distances to all other players and the number of edges created.
We augment the classical model by Interest Groups, such that every player is in exactly one of k groups, only aiming to connect to at least one player of each other group. That is, a player's cost function is dependent on the distance to each other group and the player's edges.
In both models, one is interested in equilibrium states, where none of the players can decrease its costs by creating or deleting its edges.
We study the factor between the cost of a worst case equilibrium and the optimal solution for all players (called the "Price of Anarchy").

(Introductory presentation master’s thesis)

Giuseppe Mazzuoccolo
Dipartimento di Scienze Fisiche, Informatiche e Matematiche dell' Universitá di Modena e Reggio Emilia

November 5, 2014, 2:00 pm, F1.110

Flows and bisections in cubic graphs

Given a real number r >= 2, a circular nowhere-zero r-flow (in short, an r-CNZF) in a graph G=(V,E) is an assignment f:E -> [1,r-1] and an orientation D of the edges of G, such that f is a flow in D. That is, for every vertex x \in V,  \sum_{e \in E^+(x)} f(e) = \sum_{e \in E^-(x)} f(e), where E^+(x), respectively E^-(x), are the sets of edges directed from, respectively towards x in D. Accordingly defined, the circular flow number \phi_c(G) of a graph G is the infimum number r, for which G admits an r-CNZF.
A (not necessarily proper) 2-coloring of the vertices of G is said to be a bisection if the two color classes have the same cardinality. An r-strong bisection of G is a bisection (V_1,V_2) of V such that for every set of vertices X \subseteq V, |E(X)| >= r/(r-2) * \Delta(X) where \Delta(X)=|X\cap V_2|-|X \cap V_1|.
The existence of an r-CNZF is equivalent to the existence of an r-strong bisection for a cubic graph. Circular flows in cubic graphs and equivalently r-strong bisections, give rise to very hard problems and numerous yet unsettled conjectures. Apparently, some remains highly non-trivial even when the definition of an r-strong bisections is dramatically relaxed.
A necessary condition for the existence of an r-strong bisection is that no connected subgraph on more than r-2 vertices can have the same color. With that observation in mind we now define r-weak bisection of a cubic graph G=(V,E) a bisection (V_1,V_2) of V such that for i=1,2, the subgraph of G induced by V_i does not contain a connected component on more than r-2 vertices.
Ban and Linial have recently asked which cubic graphs have 4-weak bisection. They noticed that the Petersen graph P_{10} does not admit one and conjectured that P_{10} is the only connected cubic graph that admits no 4-weak bisection. Here we prove that all cubic graphs admits a 5-weak bisection and we construct an infinite family of counterexamples to Ban-Linial conjecture and to some other related conjectures.

(Joint work with L. Esperet and M. Tarsi).

Maximilian Drees

October 29, 2014, 2:00 pm, F1.110

Why pure Nash Equilibria do not always exist in standard budget games

Standard budget games are, to some extend, a special case of weighted congestion games with player-specific utility functions. Therefore, it does not suprise that they do not necessarily posses pure Nash equilibria. However, \alpha-approximated NE do exist for these kinds of games. An \alpha-approximated Nash equilibrium is a strategy profile in which no player can improve her utility by a factor of more than \alpha by unilaterally changing her strategy.
In this talk, we show that pure NE do not always exist in standard budget games, even if we impose restrictions on the player weights. We further illustrate a technique to show the existence of \alpha-approximated NE in dependence on said restrictions. Finally, we talk about the quality of these NE as well as the existance of pure NE in special instances of standard budget games.

Shouwei Li

October 29, 2014, 2:30 pm, F1.110

Planar monotone circuit value problem and variants

Given a Boolean circuit $C$ over $n$ inputs $x_{1},\cdots,x_{n}$, and an assignment $x_{i}=a_{i}$ for each variable $x_{i}$, the Circuit Value Problem CVP is to determine the value $C$($a_{1},\cdots,a_{n}$). When each gate is labeled $NOT$, $AND$ or $OR$, CVP is complete for the complexity class $P$. It remains a $P$-Complete problem if the circuits are monotone (no $NOT$ gates) or the underlying graph has a planar embedding. However, if the circuit is simultaneously monotone and planar (MPCVP), then evaluating it is in $NC$.
In this talk, we will present an efficient parallel algorithm that evaluates PMCVP of size $n$ in polylog time using only a linear number of processors on an EREW PRAM. Then, we will re-examine the complexity of MPCVP with special attention to circuits with cylindrical embeddings. Finally, we consider extensions beyond MPCVP. We show that monotone circuits with toroidal embeddings be given can be evaluated in $NC$. Also, special kinds of arbitrary genus circuits can also be evaluated in $NC$. 

Björn Feldkord

October 22, 2014, 2:00 pm, F1.110

On variants of the page migration problem

In the classic 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 extend the classic page migration model by allowing multiple requests to occur in one time step. We provide online algorithms for different variations on this problem and show that their competitiveness ratios are asymptotically optimal.
In another approach, we want to fix the location of the page but allow adding new edges to the network for constant costs. We provide an online algorithm for the problem which is optimal up to a logarithmic factor.

(Final presentation master’s thesis)

Karlson Pfannschmidt

October 22, 2014, 2:30 pm, F1.110

Solving the aggregated bandits problem

In todays eCommerce landscape it is commonplace to let users rate goods and services. In cases where the product itself is composed of several parts produced by other companies, it is difficult to find the source of a bad overall rating.
In this master’s thesis I propose a generalization of the multi-armed bandit problem, an online learning problem where a learner is repeatedly confronted with several options to choose from. For the chosen option the learner observes a reward and the goal is to maximize the sum of rewards. In the generalization the learner can only pick pre-defined subsets of the options. Instead of receiving the reward for each option the learner is only given an aggregated reward (e.g. the average or the smallest reward). The rewards for each option are assumed to be generated by Markov processes chosen in advance by an adversary. To solve this problem the learner has to sample all the subsets efficiently while using the already gained information to model the Markov processes.

(Introductory presentation master’s thesis)

Sascha Geulen
RWTH Aachen University

October 22, 2014, 3:00 pm, F1.110

Online Learning with Switching Costs

In standard online learning, a decision maker tries to minimize his cost for an online cost-minimization problem. For this, he uses in each time step the advice of one of N experts solving the given problem. His objective is to minimize his regret, i.e., he wants to achieve an accumulated cost at most in the order of that of the best expert chosen from the set of experts in hindsight. There are many algorithms achieving this goal, but they switch the chosen expert very often.In some problems, switching between experts causes additional costs. One example is the stock market. If there are N stocks and each one is assumed to be an expert, minimizing the regret of the decision maker means finding the best stock. We developed an algorithm based on Randomized Weighted Majority which minimizes the regret of the decision maker also in this setting by changing the chosen expert rarely.

Alexander Mäcker

October 15, 2014, 2:00 pm, F1.110

Scheduling on Reconfigurable Machines With Setup Times

Moden compute centers are equipped with different types of machines to address the fact that jobs can heavily vary in their characteristics and thus, require specialized machines to be processed efficiently. Particularly the usage of reconfigurable machines (e.g. FPGAs) in addition to CPUs is becoming common practice. In order to capture these facts in a theoretical model, we consider a scheduling problem where a collection of jobs has to be processed non-preemptively on a set of $m_1 \geq 0$ identical CPUs and $m_2 \geq 0$ identical FPGAs so as to minimize the makespan. Each job comes with three parameters describing its processing time on a CPU, its processing time on an FPGA and a type. Before an FPGA is ready to process jobs of a certain type, a proper type-dependent configuration needs to be loaded onto the machine which incurs some additional setup time.
In the first part of my talk, I will present two simple polynomial time approximation algorithms for a (non-)constant number of machines. Secondly, I will focus on on-going work concerning a strategy for the case where only FPGAs are available.

Project Group DynaSearch

October 8, 2014, 2:00 pm, F1.110

Final Talk of Project Group "Dyna-Search" - P2P-Based Infrastructure for OTF-Markets

Our project group addressed the topics search and price of locality of the subproject A1 on local strategies in dynamic networks from the collaborative research center 901 "On--The-Fly Computing". Regarding search, we developed algorithms for objective function search. That is to find objects which are described by some Cartesian coordinates for which the function value of their coordinates maximizes an objective function. We have studied that problem in a setting where the Cartesian coordinate space is mapped to a peer-to-peer network. In particular, our algorithms solve that problem for linear and convex functions. Regarding price of locality, we looked at local adaption of overlay networks to communication interests of selfish agents. For this, we analyzed the convergence of network creation processes towards stable states and the quality of those states compared to solutions computed by a central instance. We especially examined this behavior under dynamic communication interests.