Research Seminar

Till Knollmann

July 6, 2022, 9:00 am, Raum: F1.310

Avoiding One vs. All -- Multi-Commodity Facilities Revisited

Remember the Multi-Commodity Online Facility Location Problem (MCOFL)? Pepperidge Farm remembers. In this problem, we consider an extension of the famous Online Facility Location Problem in which requests in a metric demand different commodities. A request must be served by an algorithm by connecting it to a set of facilities jointly offering the requested commodities. To this end, the algorithm can construct facilities for a price dependent on its location and the offered commodities. The overall goal is to minimize the total construction and connection cost.

In the past, we showed that the number of commodities |S| influences the competitive ratio an algorithm can achieve when the requests arrive over time (the problem is online). Further, we presented algorithms with a bounded competitive ratio dependent on |S|. These algorithms require a crucial condition on the construction cost function. In this talk, we are going to explore how the condition can be weakened to generalize our algorithmic results.

AND

André Graute

July 6, 2022, 9:30 am, Raum: F1.310

Neural Rendering

In this talk we present some selected state-of-the-art methods of neural realtime rendering.

AND

Gleb Polevoy

July 6, 2022, 10.00 am, Raum: F1.310

Fair, Individually Rational and Cheap Adjustment

Consider the practical goal of making a desired action profile played, when the planner can only change the payoffs, bound by stringent constraints. Applications include motivating people to choose the closest school, the closest subway station, or to coordinate on a communication protocol or an investment strategy. Employing subsidies and tolls, we adjust the game so that choosing this predefined action profile becomes strictly dominant. Inspired mainly by the work of Monderer and Tennenholtz, where the promised subsidies do not materialise in the played profiles, we provide a fair and individually rational game adjustment, such that the total outside investments sum up to zero at any profile, thereby facilitating easy and frequent usage of our adjustment without bearing costs, even if some players behave unexpectedly. The resultant action profile itself needs no adjustment. Importantly, we also prove that our adjustment minimises the general transfer among all such adjustments, counting the total subsidising and taxation.

 

Jannik Castenow & Jonas Harbig

July 01, 2022, 2:00 pm, Room: F1.110

Title: Robots Through Time and Space: Gathering & Near-Gathering

We consider a swarm of n robots in a d-dimensional Euclidean space. The robots are oblivious (no persistent memory), disoriented (no common coordinate system/compass), and have limited visibility (observe other robots up to a constant distance). The basic formation task Gathering requires that all robots reach the same, not predefined position. In the related Near-Gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, Gathering can be solved in $O(n + \Delta^2)$ synchronous rounds both in two and three dimensions, where $\Delta$ denotes the initial maximal distance of two robots [SPAA’11, Sirocco’20].

In this talk, we formalize a key property of efficient Gathering protocols and use it to define $\lambda$-contracting protocols.Any such protocol gathers $n$ robots in the $d$-dimensional space in $\Theta(\Delta^2)$ synchronous rounds. We prove that, among others, the $d$-dimensional generalization of the GtC-protocol is $\lambda$-contracting. Remarkably, our improved and generalized runtime bound is independent of $n$ and $d$.

We also introduce an approach to make any $\lambda$-contracting protocol collisionfree (robots never occupy the same position) to solve Near-Gathering. The resulting protocols maintain the runtime of $\Theta (\Delta^2)$ and work even in the semi-synchronous model. This yields the first Near-Gathering protocols for disoriented robots and the first proven runtime bound.

 

Simon Pukrop

June 22, 2022, 2:00 pm, Raum: F1.110

Scheduling with Many Shared Resources

Consider the many shared resource scheduling problem where jobs have to be scheduled on identical parallel machines with the goal of minimizing the makespan. However, each job needs exactly one additional shared resource in order to be executed and hence prevents the execution of jobs that need the same resource while being processed. Previously a $(2m/(m+1))$- approximation was the best known result for this problem.

We developed a simple and fast 5/3-approximation which I will present and a much more involved but still reasonable 1.5-approximation for which I will give the intuition. Lastly, I will present a $5/4 - \varepsilon$ inapproximability result for the natural problem extension where each job may need up to a constant number (in particular $3$) of different resources.

 

Lukas Kerkemeier

May 18, 2022, 2:00 pm, Raum: F1.110

Entwicklung, Implementation und Evaluation eines Kollisionserkennungssystems

Diese Arbeit behandelt Kollisionserkennung innerhalb von statischen Szenen. Das bedeutet, dass eine Anordnung unbeweglicher Objekte auf paarweise Überschneidungen überprüft wird. Hierzu werden verschiedene Dreieck-Dreieck-Tests, verschiedene Bounding Volumes, wie Axis Aligned Bounding Boxes und Bounding Spheres, und verschiedene Implementationen von Bounding Volume Hirarchies thematisiert, implementiert und basierend auf Benchmarks verglichen. Durch die Kombination dieser Ansätze ergibt sich abschließend eine performante Kollisionserkennung.

 

André Graute

April 29, 2022, 09:30 am, Raum: F1.110

Interactive Target Framerates in Virtual Reality

In this paper, we present an algorithm that can render virtual scenes in a user selectable rendering time. The algorithm does not work adaptively. Instead, a preprocessing is used to determine the cost of all objects in the scene in advance. Using an Octree hierarchy, we can then distribute the previously chosen budget to the nodes during the walkthrough and check whether the budget is sufficient to render the geometry of a node or to render it in an approximated way. For the approximated representation, the Blue Surfels method is used in this work.

 

Carsten De Groote

March 16, 2022, 2:00 pm, Raum: F1.110

Dispersion of Autonomous Robots on Concentric Circles inside a Circular Area

We present an algorithm for N robots to disperse inside a circular area of radius R. The robots are tasked with the dispersion inside the area such that they create R concentric circles. The distance between two robots on the same circle will be set to 1. The algorithm makes use of the provided boundary shape and inductively builds on the correctness of the positions of other robots to exactly determine the inner concentric circles. All robots are autonomous and act based on local observations. They are endowed with lights for passive communication and have a limited vision radius. They are otherwise oblivious and act fully synchronously based under the assumptions of the OBLOT model with robot lights. We prove the algorithms correctness and running time of O(R · N). We also provide some adaptions for related scenarios and discuss possible related future work in the realm of robot dispersion.

 

Till Knollmann

February 16, 2022, 3:00 pm, Raum: F1.110

Don't be picky when others aren't! -- The $k$-Server with Preferences Problem

The famous $k$-Server Problem covers plenty of resource allocation scenarios, and several variations have been studied extensively for decades. However, to the best of our knowledge, no research has considered the problem if the servers are not identical and requests can express which specific servers should serve them. Therefore, we present a new model generalizing the $k$-Server Problem by *preferences* of the requests and study the problem in a uniform metric space for deterministic online algorithms.

In our model, requests can either demand to be answered by any server (*general requests*) or by a specific one (*specific requests*). If only general requests appear, the instance is one of the original $k$-Server Problem, and a lower bound for the competitive ratio of $k$ applies. If only specific requests appear, a solution with a competitive ratio of $1$ becomes trivial since there is no freedom regarding the server's movements.

In this talk, we present our results for the competitive ratio of deterministic online algorithms on uniform metrics. We introduce a new lower bound in the general case and show a trade-off between performing well on instances of the $k$-Server Problem and performing well on instances of our generalized model. We determine a single behavioral rule that captures the trade-off and analyze its influence on the competitive ratio.

 

Jannik Castenow

January 19, 2022, 2:00 pm, Raum: F1.110

Near Gathering of Disoriented Robots with Limited Visibility and its Applications

In this talk, we present a general approach for dispersion problems of disoriented (no common coordinate system) robots with limited visibility (robots can perceive other robots only up to a constant distance).

The idea is to collect all robots within a small area at distinct locations such that every pair of robots is mutually visible (denoted as the Near Gathering problem). Afterward, the dispersion problem can be solved on a small scale by applying dispersion algorithms for robots with global visibility. Lastly, the robots can stretch their configuration to larger sizes. We will present a modification of the Go-To-The-Center algorithm to solve the Near Gathering problem and will present a first runtime bound. Afterward, first ideas of potential applications are discussed.

 

Simon Pukrop

January 12, 2022, 2:00 pm, Raum: F1.110

[Extended] Server - Cloud Scheduling on Extended Chains

In Server-Cloud Scheduling we are researching a heterogeneous scheduling model, in which we have access to both a cost free single machine server, and an unlimited rentable cloud. The goal is to schedule task graphs with regard to precedence and communication delay constraints. In an earlier paper we were able to give first results on this topic, but were restricted by the "width" of the considered task graphs.

Our current research focuses on a new graph type which consists of chains where individual nodes of the chain might be replaced by a large number of parallel jobs. We give first intuitions on ways to efficiently approximate solutions for these problems and possible extensions of the server-cloud scheduling problem.

 

Sebastian Pranger

December 15, 2021, 2:00 pm, Raum: F1.110

Online k-Facility Reallocation using k-Server Algorithms

We consider the multi-stage k-facility reallocation problem where k facilities serve n agents over T time steps. Agent locations can change every time step and facilities can be reallocated in each time step. The goal is to relocate facilities to minimize the distance from any agent to its nearest facility and the total movement of the facilities. We study an approach for solving the online version of the problem, where agent locations are revealed only for one time step at a time, by using solutions to the k-server problem, of which k-facility reallocation can be seen as a multi-stage generalization. We bring forth an online algorithm and show that its competitive ratio is nk on arbitrary Euclidean metric spaces. We also give a lower bound of n for the competitive ratio of this class of online k-facility reallocation algorithms, that are based on k-server solutions and discuss possible approaches for building an algorithm that achieves the lower bound. Finally, we simulate our algorithm to get some info on the realistic performance to put our theoretical findings into perspective.

 

Yusi Cheng

December 8, 2021, 2:00 pm, Raum: F1.110

A survey on scheduling with precedence constraints and the gap to communication delays

This is a survey on scheduling with precedence constraints and the gap to communication delays. I first summarize the current state of precedence constrained scheduling problems and several common methods. When communication delays are introduced, the complexity of some problems changes. Some methods are modified in order to deal with communication delays, while some new methods are created. In the end, I write a Python program to simulate two approximation algorithms and compare them.

 

Barbara Kempkes und Andreas Cord-Landwehr

November 26, 2021, 17:00 Uhr, F0.530

Alljährliches Kooperationskolloquium

Die beiden Vortragenden unseres diesjährigen Kolloquiums sind Absolventen unserer Arbeitsgruppe. Sie berichten über ihre aktuellen Tätigkeitsfelder in der industriellen und wissenschaftlichen Praxis.

Barbara Kempkes promovierte im Jahr 2012 in unserer Arbeitsgruppe mit einer Arbeit über „Local strategies for robot formation problems“. Sie ist heute bei der dSPACE GmbH in Paderborn tätig.

Andreas Cord-Landwehr promovierte im Jahr 2016 in unserer Arbeitsgruppe mit einer Arbeit über Selfish Network Creation - On Variants of Network Creation Games. Er ist heute bei der CLAAS KGaA mbH in Harsewinkel tätig.

 

Maximilian Beck

November 17, 2021, 2:00 pm, Raum: F1.110

Parametergesteuerter Algorithmus zur Grundrissgenerierung für mehrstöckige Gebäude

In dieser Arbeit wird eine prozedurale Generierungsmethode für Grundrisse von mehrstöckigen Gebäuden präsentiert. Die Eingabe umfasst eine Gebäudehülle und die Gebäudecharakteristiken, durch die die Generierung gesteuertwird. Durch einen Scan der Gebäudehülle werden die Stockwerke und die Ressourcen des Gebäudes erfasst und in eine Gitterdarstellung übertragen. Die Räume werden über ein ressourcenbasiertes Platzierungsverfahren in den Stockwerken positioniert. Über eine wachstumsbasierte Methode werden die Räume vergrößert, bis die gesamte Stockwerkfläche eingenommen ist. Die Erreichbarkeit der Räume wird durch das Platzieren von Türen, Treppenhäusern und Korridoren sichergestellt.

AND

Jonas Harbig

November 17, 2021, 2:45 pm, Raum: F1.110

Grid in The Box - A Swarm Formation Problem

We assume a swarm of N robots according the LUMINOUS model on an Euclidean plane placed inside a rectangle of size W x H. The robots have no common orientation, each has its own self-centered coordinate system with arbitrary rotated/mirrored axis, and only a local view where they can observe other robots and the sides of the rectangle. They act in look-compute-move cycles in fully synchronous rounds (FSYNC). Starting on arbitrary unique positions inside the rectangle the robots form a regular grid parallel to the rectangle's sides in O(N) rounds. If N = H*W + O(H+W) the grid will fill the whole rectangle, less robots will result in a partial grid and more robots will expand the grid further outside the rectangle.

 

Bogna Wierzbinska

October 13, 2021, 11:00 am, Raum: FU.511

Max-Chain-Fomation für Roboterschwärme auf dem Gitternetz im LUMINOUS Model

In dieser Arbeit sehen wir uns das Max-Chain-Formation-Problem im Gitter an. Dabei sind n Roboter in einer offenen Kette gebunden. Die Roboter arbeiten nach dem Fsync LUMINOUS Model, bei denen die Roboter über eine begrenzte Anzahl an Lichtern zur Kommunikation verfügt.

Die Aufgabe der Roboter ist das Lösen des Max-Chain-Formation-Problem, bei dem der Abstand zwischen den Endrobotern maximieren werden soll. In dieser Arbeit wird eine Lösung präsentiert, bei denen sich die Roboter in einer horizontalen oder vertikalen Gerade ausrichten. Diese Umformung der Kette ist dabei in linearer Zeit möglich, und es ist dabei möglich stets den maximalen Abstand n zu erhalten.

 

Thilo Frederik Berger

October 11, 2021, 11:00 am, Raum: F0.530

Combining Mobility, Heterogeneity, and Leasing Approaches for Online Resource Allocation

In the online facility location problem, we have a set of possible facility locations and a set of requests which arrive over time. The task for an algorithm of this problem is to connect the requests to facilities upon their arrival and try to minimize the resulting cost arising due to the opening of facilities and connecting the requests. In this thesis, we combine three different extensions of this problem to find out whether a combination is possible and if the different extensions work independently of each other.

The first extension of this model is the online multi-commodity facility location problem, which gives facilities the choice of which commodities they offer out of a total set S. In this problem, requests need to be served by facilities that jointly cover the requested commodities.

The second approach is online facility leasing, in which facilities are only open temporarily for different lease durations. The lease duration of a facility can be chosen from a set of lease types and is fixed once a facility is open.

The last approach is the mobile facility extension which gives the online algorithm the ability to move already open facilities. This ability is used to achieve a competitive ratio independent of n.

To combine all extensions into a single model we create a randomized algorithm for the online facility leasing extension as to the best of our knowledge no such algorithm exists. Combining all three randomized algorithms is possible and mostly straightforward as the algorithm are mostly independent of each other with only a minor part of the analysis standing out. The competitive ratio we achieve by combining them is

O(( log D log log D) ·√|S|+min{` ·√|S|,|S|·√`}) ·|K|),

the part which deviates from simply combining the additional factors of the different extension is the the min-term. If the algorithm were completely independent the min-term would instead be √`·√|S| with the first half coming from the mobile facility extension and √|S| coming from the online multi-commodity problem.

Additionally to the combination of the randomized algorithm, we also combine the deterministic algorithm of the online multi-commodity problem and the online facility leasing extension. The deterministic algorithm are independent of each other giving us the upper bound of O(log n ·√|S|·|K|), with √|S|.