# Research Seminar

## Winterterm 2018/19

#### (New Date !)  January 23, 2019, 16:00 pm, F0.530

Introduction to Multi-Operation Jobs with Setups on a Single Machine

In this talk, we will have a look at a realistic, but not much researched, scheduling setting, which is the subject of my master thesis. In the problem class we consider composed jobs represented by a set of operations, which themselves are ordered into different families. When scheduling operations of different families back to back, one induces additional costs in the form of a setup time. We describe the quality of a schedule by its total completion time. I will give an overview of already known properties of this setting and share my current research about adapting and creating algorithms to solve or approximate different subclasses of this problem.

#### January 16, 2019, 14:00 pm, F1.110

Performance Optimization for Flight Simulation through Culling Algorithms

In this talk I will provide an outlook on my master thesis on occlusion culling for flight simulators. My thesis is aimed at developing occlusion culling algorithms for flight simulators that take advantage of the occlusion provided by the virtual cockpit of home entertainment flight simulators as well as of nearby mountains and ridgelines occluding other parts of the scenery. I will outline the evolution of modern flight simulators and why they seem like bad candidates for occlusion culling. I will furthermore present scenarios in flight simulation were occlusion culling can make sense despite the seeming unsuitability of flight simulators for occlusion culling.

#### January 16, 2019, 14:30 pm, F1.110

Evaluation and Impressions of the RESIBES Ad Hoc Network Field Experiments

As part of the RESIBES project for disaster relief coordination, we developed an ad hoc network library for Android apps. In contrast to other efforts in this area, we didn't use system level approaches here, which need special execution privileges, but instead we implemented a store-carry-forward approach based on Google Play Nearby. This can be used by any app on a device that has Google Apps installed and makes it possible to distribute apps using our library over the Google Play Store. In this talk I will share the setup and some impressions of our field experiments in 2018, as well as our evaluation about the performance and reliability of our approach.

#### January 9, 2019, 14:00 pm, F1.110

Caching of points for the Blue Surfels Approach

In this talk, we discuss the technique used to render highly complex 3D scenes in real time by generating uniformly distributed points on the scene's visible surfaces. These uniformly distributed points are then displayed thereby allowing for progressive refinement of the number of rendered points based on the position of the camera. This talk will briefly discuss about the approach followed by the Blue Surfels paper and conclude with possible enhancement ideas.

(Introductory talk Masters thesis)

#### January 9, 2019, 14:30 pm, F1.110

Procedural generation of urban buildings road networks
(Prozedurale Generation von Urbanen Straßennetzen)

Building a realistic man-made city is a significant challenge in computer graphics. And a realistic urban-street-network is the foundation of a realistic man-made city. In this paper, a system is introduced which uses a procedural method to build an urban-street-network.  The input of this system is the outline of a city, which is represented by a loop of directed segments. The shape of the given city will be analyzed autonomously to generate an urban-layout for the city, namely an urban-street-network of the city. All urban-street-network schemes obtained through this system are based on the urban planning model – Sector Modell and are planned randomly in a radial shape. The main algorithm used by the system is a mechanism which is similar to the L-system, and at the same time the tensor fields is also used by the system to control the generation-direction of the urban-street-network, so that the entire urban-street-network can be generated automatically without human intervention.

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

#### December 19, 2018, 14:00 pm, F1.110

On the Influence of Payments in Congestion Games

The strategic interaction between clients in markets are often modelled with the theoretical framework of congestion games. In these games, each player chooses a strategy, which is a set of resources and gets payoff, depending on her and her peers' strategies. For this class of games, pure Nash equilibria always exist. However, for some situations, a class of games allowing a more detailled modelling is desirable. To address this issue, we extend the class of congestion games, creating a new model, that makes use of payments. In our new model, players still choose a subset of resources as their strategy, but in addition to choosing which resources to use, they also choose what payment to make for each resource of their choice. For a resource, the more a player pays, the more payoff she gets. We investigate this new class in game theoretic manner and prove that it does not always admit a pure Nash equilibrium. Additionally, we prove existence of such equilibria for two derivatives of our model, that use a fixed payoff function and differ in whether players are only allowed to use discrete values as payments. We also provide an algorithm to compute an equilibrium assuming that each player can use each resource. Furthermore we show that pure Nash equilibria exist for generalizations of two existing models, that are market sharing games and complete flow networks.

#### December 19, 2018, 14:45 pm, F1.110

Which Soda should Sally sell? – The Online Multi-Commodity Facility Location Problem

We consider the Multi-Commodity Facility Location Problem as an extension of the Facility Location Problem (FLP). The model is similar to the FLP, i.e, requests are located at points of a metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogenous, they request or offer multiple types out of a finite typeset. For example, this allows to model a situation where clients in a city demand for different kind of soft-drinks and a company aims at placing vending machines offering various soft-drinks at suitable locations. In comparison to the FLP, an algorithm not only has to decide where and how many facilities to place, but also what types to offer at each. We study the problem in its online variant where requests and their positions/types are revealed over time. In this context, we present first results regarding the competitiveness ratio. On the one hand, we show a deterministic online algorithm with a competitiveness of $$O( \log n + |S| )$$, on the other hand, we construct a lower bound on the competitiveness for any randomized online algorithm of $$\Omega ( (\log n)/(\log \log n) + \sqrt{|S|} )$$. In both cases $$n$$ is the number of requests while $$|S|$$ is the total number of types.

#### December 12, 2018, 14:00 pm, F1.110

Runtime Gap of the Max-GTM Strategy

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 outer robots 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 analyze the Max-GTM strategy that transforms the initial chain into a straight line of length n-1. We show that the lower bound for transforming an initial chain in two dimensions depends on the initial distance of the outer robots. Since the upper bound for one dimensional chains is O(n² log 1/epsilon), this introduces a runtime gap for one- and two-dimensional chains. Lastly, we show an upper bound of O(n² log 1/epsilon) for the case in which only one outer robot moves.

#### November 30, 2018, 5:00 pm, F0.530

Weihnachtsseminar - Algorithmen und Komplexität

Kay Salzwedel wird einen Vortrag im Rahmen des Weihnachtsseminars der Arbeitsgruppe Algorithmen und Komplexität halten. Kay Salzwedel ist ehemaliger Mitarbeiter von Friedhelm Meyer auf der Heide. Er promovierte im Jahr 2004 bei Friedhelm Meyer auf der Heide mit dem Thema Datenverteilung und Speichernetzwerke. Jetzt arbeitet er bei der Audi AG in Ingolstadt und beschäftigt sich mit dem Anforderungsmanagement für Neufahrzeuge. Er wird einen Überblick über sein Tätigkeitsfeld geben.

#### November 21, 2018, 02:00 pm, F1.110

Approximating Maximum Flow Time on a Machine with Setup Times

Consider a problem in which $n$ jobs that are classified into $K$ types are to be scheduled on a single machine. The machine requires a setup taking $s_k$ time units whenever it switches from processing jobs of a type $k' \neq k$ to jobs of type $k$. Each job has a release time before which it cannot be processed and the goal is to minimize the maximum flow time, given by the largest difference of a job's finishing time and its release time.

In this talk, we consider the offline version of this problem where the scheduler knows all jobs in advance and discuss some ongoing work on an approximation algorithm.

#### November 7, 2018, 02:00 pm, F1.110

On the Feasibility of a k-Mobile Server Problem

We discuss the k-Mobile Server Problem, an extension of a model where one server in the Euclidean plane serves requests over time which induces costs proportional to the distance between server and request. The server may be moved a limited distance in each round.
In our extension, we have k servers which may be moved a limited distance each (for every time step). We show that no competitive algorithm can exist without severe restrictions in the model and an augmented maximum movement distance for the online algorithm. For a restricted variant, we discuss possible algorithms based on existing algorithms for related problems and a starting point for the analysis.

#### October 24, 2018, 02:45 pm, F1.110

Sampling Surfels on the GPU and View-dependent Progressive Point Rendering

In this talk I present current research advancements in the context of our paper "Rendering of Complex Heterogeneous Scenes using Progressive Blue Surfels". On the one hand I will present a simple method to achieve view-dependent level-of-detail rendering of progressive points, on the other hand I will present ideas and first results for visibility-aware resampling of objects into progressive point clouds entirely on the GPU.

#### October 8, 2018, 11:00 am, F2.211

Smartphone-based Communication Networks for Emergency Response

Lars Almon is responsible for the project Smarter: Smartphone-based Communication Networks for Emergency Response [1]. Smarter is a solution for infrastructure-independent emergency communication via smartphones. If the communication infrastructure fails in the event of a crisis or disaster, citizens should be able to communicate with each other and with the authorities and organisations with security tasks (BOS) via Smarter. Lars Almon will report on the project and present the developed solutions.

(talk is given in German)

[1] smarter-projekt.de