Research Seminar

Summer Term 2018

Alexander Mäcker

May 2, 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.

Björn Feldkord

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.

Sascha Brandt

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.