Research Seminar

Winterterm 2018/19

Jannik Sundermeier

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.

Kay Salzwedel

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.

Alexander Mäcker

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.

Björn Feldkord

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.

Sascha Brandt

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.

Lars Almon
Technische Universität Darmstadt, Department of Computer Science, Secure Mobile Networking Lab - SEEMOO

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)