Wintersemester 2019/2020

Martin Ziegler
Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Südkorea

December 18, 2019, 2:00 pm, F1.110


Marten Maack
Christian-Albrechts-Universität zu Kiel

December 13, 2019, 9:00 am, F0.225

Inapproximability Results for Scheduling with Interval and Resource Restrictions

In the restricted assignment problem, the input consists of a set of machines and a set of jobs each with a processing time and a subset of eligible machines. The goal is to find an assignment of the jobs to the machines minimizing the makespan, that is, the maximum summed up processing time any machine receives. Herein, jobs should only be assigned to those machines on which they are eligible. It is well-known that there is no polynomial time approximation algorithm with an approximation guarantee of less than 1.5 for the restricted assignment problem unless P=NP. In this work, we show hardness results for variants of the restricted assignment problem with particular types of restrictions.

In the case of interval restrictions the machines can be totally ordered such that jobs are eligible on consecutive machines. We resolve the open question of whether the problem admits a polynomial time approximation scheme (PTAS) in the negative (unless P=NP). There are several special cases of this problem known to admit a PTAS.

Furthermore, we consider a variant with resource restriction where each machine has capacities and each job demands for a fixed number of resources. A job is eligible on a machine if its demand is at most the capacity of the machine for each resource. For one resource, this problem is known to admit a PTAS, for two, the case of interval restrictions is contained, and in general, the problem is closely related to unrelated scheduling with a low rank processing time matrix. We show that there is no polynomial time approximation algorithm with a rate smaller than 48/47 or 1.5 for scheduling with resource restrictions with 2 or 4 resources, respectively, unless P=NP. All our results can be extended to the so called Santa Claus variants of the problems where the goal is to maximize the minimal processing time any machine receives.

Nils Luca Rudminat

04. Dezember 2019, 14.00 Uhr, F1.110

Analyse des Online Facility Location Problems mit mobilen Facilities

Beim ursprünglichen Facility Location Problem sind eine Menge von Requests und eine Menge von möglichen Facility Locations im metrischen Raum gegeben. Die Aufgabe ist es, eine Teilmenge der Facility Locations anzugeben und jede Request mit einer Facility aus der gewählten Menge zu verbinden, wobei Kosten für das Bedienen der Requests (die Distanz zu der verbundenen Facility) und das Eröffnen der Facilities entstehen. Das Ziel ist es, die Gesamtkosten zu minimieren.

Anders als beim ursprünglichen Facility Location Problem werden in diesem Vortag Algorithmen für zwei online Varianten vorgestellt, bei denen die Requests nacheinander ankommen und es auch möglich ist, die ursprüngliche Position einer Facility zu verändern. In der ersten Variante entstehen dabei keine Kosten für das Verschieben der Facilities, aber die Distanz, um welche eine Facility verschoben werden darf, ist begrenzt. In der zweiten Variante ist die maximale Verschiebedistanz nicht mehr beschränkt, allerdings entstehen konstante Kosten für jede Bewegung einer Facility. In beiden Varianten wird dabei vom etwas spezifischeren euklidischen Raum und von uniformen Eröffnungskosten der Facilities ausgegangen. Außerdem müssen Requests nach deren Ankunft unwiderruflich einer Facility mit entsprechenden Bedienkosten zugeordnet werden.

Jaroslaw Kutylowski und Martin Ziegler
DeepL GmbH, Köln und Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Südkorea

November 22, 2019, 17:00 pm, F0.231

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.

Jaroslaw Kutylowski ist Mitgründer und Geschäftsführer (CEO) der DeepL GmbH in Köln. Er leitete die Einführung des Dienstes DeepL Pro. DeepL ist der derzeit beste Dienst im Bereich der automatischen Sprachübersetzung. Er richtet sich an professionelle Benutzer und hat sich als ein wichtiger Player im KI-Sektor etabliert. Jaroslaw Kutylowski promovierte im Jahr 2007 in unserer Arbeitsgruppe. Seine Dissertation begründete unseren Forschungsschwerpunkt über algorithmische Grundlagen von Roboterschwärmen.

Martin Ziegler ist Professor für Theoretische Informatik am Korea Advanced Institute of Science and Technology (KAIST) in Südkorea. Vorausgegangen sind wissenschaftliche Aufenthalte in Dänemark, Japan, Österreich. Seine Forschung dreht sich um algorithmische Grundlagen der Numerik: von Berechenbarkeit über Komplexität und Logik bis Computerphysik. Martin Ziegler promovierte im Jahr 2004 in unserer Arbeitsgruppe mit einer Arbeit über die Berechenbarkeit reeller geometrischer Probleme. Seine Habilitation erfolgte 2008 an der Universität Paderborn.

Björn Feldkord

new Date: November 20, 2019, 14:00 pm, F1.110

Mobile Resource Allocation

We consider applications involving many users who upload data over the internet. In order to minimize response times, we seek to place instances of the corresponding service close to the users, however each instance of the service comes at a cost, and relocating induces cost proportional to the distance an instance is being moved. In addition, we only allow services being migrated over a limited distance.

In the first part of the talk, I will briefly summarize the findings of my PhD project concerned with the above problem. The theoretical models are close to classical problems such as the k-Server and Online Facility Location problems. In the second part, I will discuss potential future research based on the work done so far as well as other interesting approaches in the broad area of resource allocation.

Till Knollmann

October 30, 2019, 14:00 pm, F1.110

A Matter of Taste – Dealing with requests for different types

We present current results on the Online Multi-Commodity Facility Location Problem (OMFLP) in metric spaces. In comparison to the Online Facility Location Problem (OFLP), the OMFLP considers the case that requests have a type out of a finite type set S. An arriving request has to be assigned immediately to a facility serving its type incurring an assignment cost and construction costs for facilities depending on the set of types and the position where a facility is opened. The task is to minimize the total assignment and construction cost.

In earlier talks we showed a lower bound involving the length of the request sequence as well as the number of types. In this talk, we are going to present a deterministic algorithm for the OMFLP with non trivial competitiveness. Further, we are going to discuss special cases where the competitiveness changes depending on restrictions to the cost function and introduce changes to the model raising interesting new problems for future research.

Jannik Castenow

October 16, 2019, 14:00 pm, F1.110

Stretching a Communication Chain of Oblivious Mobile Robots — The Continuous Case

In the talk, we consider the problem of arranging a communication of n robots on a straight line of length n-1. The robots have a limited viewing range of 1, do not agree on a coordinate system or compass and are oblivious. In contrast to previous talks about this problem, we consider the continuous time model in which robots can continuously observe their environment and can immediately adjust their own trajectory based on their observations. We introduce the Max-Move-On-Bisector strategy, analyze its behavior in one-dimensional configurations and give insights about the current state of research about two-dimensional configurations.

Sascha Brandt

October 09, 2019, 14:00 pm, F1.110

Visibility-Aware Progressive Farthest Point Sampling on the GPU

In this talk, I present the first algorithm for progressive sampling of 3D surfaces with blue noise characteristics that runs entirely on the GPU. The performance of the algorithm is comparable to state-of-the-art GPU Poisson-disk sampling methods, while additionally producing ordered sequences of samples where every prefix exhibits good blue noise properties.

The basic idea is, to reduce the 3D sampling domain to a set of 2.5D images which we sample in parallel utilizing the rasterization hardware of current GPUs. This allows for simple visibility-aware sampling that only captures the surface as seen from outside the sampled object, which is especially useful for point-based level-of-detail rendering methods. However, the method can be easily extended for sampling the entire surface without changing the basic algorithm. I provide a statistical analysis of our algorithm and show that it produces good blue noise characteristics for every prefix of the resulting sample sequence and analyze the performance of the method compared to related state-of-the-art sampling methods.

Sommersemester 2019