Summer Term 2018

Patrick Irenaeus KOLPACZKI

September 24, 2018, 02:00 pm, F1.110

Transforming the Double Coverage Algorithm from the k-Server Problem to the k-Page Migration Problem

We consider the Online k-Page Migration Problem in which single requests arrive in metric space and have to be served by the nearest of k pages before the next one arrives with costs equal to the distance from that page to the request. The pages can be moved once before serving a request incurring costs equal to the distance moved multiplied by a factor D. Motivated by its simplicity we transform the deterministic Double Coverage Algorithm for the well studied Online k-Server Problem to recieve an online algorithm for the k-Page Migration Problem on the line and bound its competitiveness via a parameterized potential function analysis and the adversary technique between 0,5k and 5k+3. Additionally we use the same approach to construct an online algorithm for the File Migration Problem on the circle using only one page and derive tight bounds for its competitiveness depending on D and differing only by an additive constant. Following we simulate the first online algorithm against a developed brute force offline solution with algorithmic performance improvements. The gathered data proves our analysis to be reasonable precise against the first impression that the results are just an arbitrary product of mathematical relations underlying in the chosen case distinction of the analysis. Furthermore they provide us with a deeper insight into the behavior of the algorithm regarding competitiveness and average costs depending on k and D.

(The talk will be held in German)


September 19, 2018, 02:00 pm, F1.544

Mobile Facility Leasing

In this variant of the well-studied Online Facility Location Problem, facilities are rented temporarily by purchasing tickets that expire after their respective lifetime. Upon their arrival, each request must be assigned to a nearby facility, inducing costs equal to their Euclidean distance. Additionally, any online algorithm may adjust the positioning of its facilities, paying costs proportional to the covered distance. By proposing and analyzing an online algorithm for this problem, upper and lower bounds on the competitive ratio that are independent of the number of clients can be achieved.

(The talk will be held in German)


September 11, 2018, 11:00 am, F2.211

Influence of Stationary Robots on Continuous Robot Formation Problems

We consider a group of n autonomous mobile robots of which m are stationary thus cannot move. Robots are represented by points in the Euclidean plane. They have no memory, do not communicate or share a common coordinate system and they move solely based on the positioning of other robots within their limited viewing range of 1. The goal is to gather the robots inside of the convex hull of all stationary robots. A variant of this problem, the general gathering problem, has been studied in various different time models. In this work, we consider a continuous time model, where robots continuously observe their neighbors, compute the next target of movement and move with a speed limit of 1 at any time. Regarding the robots’ local strategy, we only study contracting algorithms in which every robot that is positioned on the border of the convex hull of all robots moves into this hull. We present a time bound of O(nd) for any general contracting algorithms in a configuration with only a single stationary robot. For configurations with more stationary robots, we prove that robots converge against the convex hull of all stationary robots and that no upper bound on the runtime exists. For the specific contracting algorithms Go-To-The-Left, Go-On-Bisector and Go-To-The-Middle, we provide linear time bounds.

Martin Ziegler
KAIST School of Computing

August 13, 2018, 11:00 am, F1.110

Game Theory, In-/Stability, and Conflict/Peace Science

We reconsider the Game-theoretic foundation to Deterrence Theory as employed by Herman Kahn and Thomas Schelling during the Cold War: Borrowing from metric geometry/numerical analysis, we define and investigate "Condition Numbers" as first quantitative measures of in-/stability for games capturing international relations in Conflict/Peace Science.

(Joint work with Christopher Fichtlscherer)

Till Knollmann

June 27, 2018, 2:00 pm, F1.544

Multi Dimensional Range Queries and how to answer them

We present a Peer-to-Peer network that supports the efficient processing of d-dimensional orthogonal range queries R=\times_{i=1}^{d} [a_i, b_i]. The  network is the same for each dimension, namely a Distance Halving Network like the one introduced by Naor and Wieder in "Novel Architectures for P2P Applications: the Continuous-Discrete Approach" (2006). We show how to execute such range queries using O(2^{d'} d \log m + d |R|) hops (and the same number of messages) in total. Here [m]^d is the ground set, |R| is the size and d' the dimension of the queried range. Furthermore, if the peers form a distributed network, the query can be answered in O(d \log m + d \sum_{i=1}^{d} |a_i-b_i|) communication rounds. Our algorithms are based on a mapping of the Hilbert Curve through [m]^d to the peers.

Marcus NAchtigall

June 20, 2018, 2:00 pm, F1.544

Evaluating algorithms for multiprocessor scheduling with sharable resources

In my Master-Thesis, I will consider the multiprocessor scheduling problem in an extended setting where additional (sharable) resources are available. Therefore, jobs do not only require a processor, but also require a certain amount of work on (a subset of) the additional resources. Hence, a scheduler has to do an assignment of jobs, processors and the additional resources.
In the first part of the thesis, the model considers the multiprocessor scheduling problem with one sharable resource. For this problem, there already exists an algorithm with theoretical analysis, which also proves its approximation factor. Compared to this theoretical analysis, the algorithm will be implemented, simulated and evaluated with respect to the results of the simulation. As the input to the simulated algorithms should be as realistic as possible, these data are generated by emulating real applications on a cluster of computers. In the second part of this thesis, the model will be generalized such that there is not only one sharable resource, but k sharable resources. For this problem, a new algorithm will be designed, which then will be simulated and evaluated. Furthermore, the algorithm will be analyzed theoretically and it will be tried to prove the approximation factor.

Jonas Harbig

June 13, 2018, 2:00 pm, F1.544

Gathering Strategy for Mobile Robot Swarms in a Grid - Research on Fault Tolerance

For a swarm containing $n$ autonomous robots, gathering on one point is a basic problem. Swarm robots have to be cheap and therefore it is likely that one will be faulty. An example for a faulty one is a stationary robot which never moves. For a gathering algorithm it is important to be tolerant to such a fault.
In [FJH17] an algorithm is described which allows a swarm of robots to gather at a $2\times2$ square. All robots are anonymous, oblivious and do not communicate. They are located in a grid, have a viewing range of 7 ($L_1$ distance) and act fully synchronous in look-compute-move cycles. Look: save a snapshot of the environment. Compute: decide based on the snapshot to move or not. Move: perform the move. In every round a robot can move to any horizontal, vertical and diagonal neighboring grid cell. In this thesis we apply a small change to the algorithm, such that a swarm which contains one stationary robot gathers at that robot. We formally prove that the gathering is finished in $\mathcal{O}(n^2)$ rounds. Further we analyze the behavior of a swarm which contains more than one stationary robot. The swarm can naturally not gather at one point. We show that such a swarm is after $\mathcal{O}(n^4)$ rounds located in a $f(e)\times f(e)$ square, where $e$ is the maximum distance between two stationary robots and $f(e)$ is in $\Theta(e)$. In some constellations the swarm never becomes static, however the location of the remaining moving robots is limited. A formal proof is given that no robot outside of the convex hull over all stationary robots will perform another move after $\mathcal{O}(n^4 + 2^{e^2})$ rounds.

(The talk is in German)

Fischer, Matthias; Jung, Daniel; Meyer auf der Heide, Friedhelm: Gathering Anonymous, Oblivious Robots on a Grid. In: The 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, 2017

Jannik Sundermeier

June 6, 2018, 2:00 pm, F1.544

Maximizing a Chain of Oblivious Mobile Robots

We consider a chain of point-shaped mobile robots distributed in the Euclidean plane.
In the chain, every inner robot has exactly two neighbors, whereas the endpoints of the chain only have a single neighbor.
The chain itself can be arbitrary winding and even self-intersecting.
Additionally, every robot has a limited unified viewing range of $1$.
We propose a strategy that transforms a chain of mobile robots into a maximum chain.
More precisely, the chain of $n$ robots has to be transformed into a straight line of length $n-1$.
The time is divided into fully synchronous Look-Compute-Move-Cycles in which each robot periodically observes its environment,
computes a target position and finally moves to the target point.
Every move is solely based on the observation of the current round (the robots are oblivious).
Provided the robots are already positioned on a straight line, we show that our strategy
needs at least $\Omega(n^2 \log 1/\varepsilon)$ and at most $\mathcal{O}(n^3)$ rounds to be close to the maximal straight line.
Our lower bound matches the lower bound of a similar strategy in a model in which the endpoints of the chains are stationary.
Furthermore, we give some intuition why the proof cannot be directly translated to an arbitrary winding chain in the Euclidean

Matthias Feldotto

May 30, 2018, 2:00 pm, F1.544

Disaggregating User Evaluations Using the Shapley Value

We consider a market where final products or services are compositions of a number of basic services. Users are asked to evaluate the quality of the composed product after purchase. The quality of the basic service influences the performance of the composed services but cannot be observed directly. The question we pose is whether it is possible to use user evaluations on composed services to assess the quality of basic services. We discuss how to combine aggregation of evaluations across users and disaggregation of information on composed services to derive valuations for the single components. As a solution we propose to use the (weighted) average as aggregation device in connection with the Shapley value as disaggregation method, since this combination fulfills natural requirements in our context. In addition, we address some occurring computational issues: We give an approximate solution concept using only a limited number of evaluations which guarantees nearly optimal results with reduced running time. Lastly, we show that a slightly modified Shapley value and the weighted average are still applicable if the evaluation profiles are incomplete.

Johannes Schaefer

May 23, 2018, 2:00 pm, F1.544

On the current state of things of RESIBES

I will give an overview of the current design of the ad hoc network layer of the RESIBES app, the design choices made, and show the current implementation.
In RESIBES , a smart phone app will be developed that allows relief agencies to communicate with the registered helpers. In absence of disasters methods of communication are necessary as to enable the agencies to keep people interested and motivated in the app. This will lead to the people keeping information up-to-date and the app installed on their phones.
We are aiming at building a resilient network, i.e. even with a high mobility of participants, chances of devices dying due to empty batteries, etc., the network still works as a communication layer. Also, we explore methods which allow restoring or improving connectivity by placing devices on strategically relevant places.

Alexander Mäcker

May 9, 2018, 2:00 pm, F1.544

Scheduling on (Un-)Related Machines with Setup Times

We consider a scheduling problem in which $n$ jobs need to be processed on parallel machines so as to minimize the makespan. The set of jobs is partitioned into classes and a setup needs to take place whenever a machine switches from processing a job of one class to a job of a different class. While for the case of identical machines approximation algorithms with best possible approximation factors are known, there are not yet any results for the case of non-identical machines. The two models for non-identical machines most common in literature are uniformly related machines and unrelated machines. In the former case, each machine has a fixed speed while in the latter one processing times can vary arbitrarily between different machines.
In this talk, we will particularly see that the unrelated machines problem (even in its restricted assignment variant) can only be approximated to within a factor of $\Theta(\log n)$. This is in stark contrast to the classical model without setup times for which the approximation factor lies somewhere in $(3/2, 2]$. We will also discuss a natural special case of the restricted assignment variant for which we can give a $2$-approximation.

Marcin Bieńkowski

May 2, 2018, 2:00 pm, F1.544

University of Wrocław
Institute of Computer Science, Combinatorial Optimization Group

On phase-based algorithms for online file migration

We construct a deterministic 4-competitive algorithm for the online file migration problem, beating the currently best 20-year old, 4.086-competitive Move-To-Local-Min (MTLM) algorithm by Bartal, Charikar and Indyk (SODA 1997). Like MTLM, our algorithm also operates in phases, but it adapts their lengths dynamically depending on the geometry of requests seen so far. The improvement was obtained by carefully analyzing a linear model (factor-revealing LP) of  a single phase of the algorithm. We also show that no fixed-length phase-based  algorithm can beat the competitive ratio of 4.086.

Joint work with Jarek Byrka and Marcin Mucha, published at ICALP 2017.

Björn Feldkord

April 18, 2018, 2:00 pm, F1.544

Mobile Facilities and Infinite Servers - Augmentation of Classical Online Problems

We consider the following extension of the Online Facility Location Problem: Facilities may be opened for fixed costs and incoming demands must be satisfied immediately by connecting them to an open facility. In addition, an online algorithm may move facilities for costs proportional to the respective distance. We show that under these conditions it is possible to derive upper bounds on the competitive ratio which are independent of the number of clients.
Next, we discuss the possibility of granting the ability to move facilities to the offline solution as well. We introduce variants of the k-Server Problem which are closely related to this problem and give some intuition about possible solutions.

Sascha Brandt

April 11, 2018, 2:00 pm, F1.544

Rendering of massive 3D scenes with continuous level-of-detail and why hierarchies are bad

Traditionally, when rendering large complex 3D scenes in real-time, the scenes are partitioned into a spacial hierarchy (e.g., octree, bsp-tree, kd-tree) and each node of the hierarchy references a discrete approximation of the subtree that is contained within this node. During scene traversal for rendering we can now simply render the approximation instead of the subtree to reduce rendering time while sacrificing visual fidelity.
This method can be very memory consuming and inflexible for large scenes. Other methods are available that allow a continuous adjustment of the approximation quality for each scene object while having a much lesser memory requirement without the need for an explicit hierarchy. However, when rendering 3D scenes that contain a massive amount of geometric objects, it becomes very difficult to manage such approximations. This talk presents the challenges that arise when rendering massive 3D scenes with continuous level-of-detail, using the example of Progressive Blue Surfels, and discusses possible solutions to these challenges.