# Research Seminar

## Summer Term 2018

#### 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.

#### 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.

#### 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)

[FJH17]
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

#### 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
plane.

#### 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.

#### 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.

#### 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.

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

###### University of WrocławInstitute 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.

#### 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.

#### 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.