„Packen und Schedulen mit Gütegarantien“

Scheduling- und Packprobleme gibt es in vielen Anwendungsbereichen. Rob von Stee befasst sich hauptsächlich damit, Algorithmen mit beweisbaren Gütegarantien hierfür zu entwerfen.


Informatik-Kolloquium am 19. Mai in der FernUniversität

Um das „Packen und Schedulen mit Gütegarantien“ geht es in dem Vortrag, den PD Dr. Rob van Stee am Montag, 19, Mai, im Informatik-Kolloquium der Fakultät für Mathematik und Informatik der FernUniversität in Hagen hält. Die Veranstaltung findet im AVZ-Gebäude, Universitätsstr. 21, 58097 Hagen, 1. OG, Raum B121 (Großer Senatssaal) ab 11 Uhr statt.

Scheduling- und Packprobleme gibt es in vielen Anwendungsbereichen. In seiner Forschung beschäftigt sich Rob von Stee hauptsächlich damit, Algorithmen mit beweisbaren Gütegarantien für solche Probleme zu entwerfen, zum Beispiel Approximations- oder Online-Algorithmen. Ein klassisches Problem in diesem Gebiet ist Bin-Packing. Gegeben ist eine Eingabesequenz von Objekten (Items) mit unterschiedlichen Größen, die in möglichst wenig Behälter (Bins) gepackt werden müssen. Das ganze Forschungsgebiet der Approximationsalgorithmen hat mit Bin-Packing-Algorithmen angefangen. Seit 40 Jahren war der beste Online-Algorithmus First Fit. Der Referent wird einen neuen Algorithmus vorstellen, der First Fit schlägt und ein optimales Kompetitivitätsverhältnis hat.

Gerd Dapprich | 30.04.2014