Hörsaal M/E28, Mathematik-Gebäude

Fluss- und Routingprobleme gehören zu den klassischen Fragestellungen der diskreten Mathematik. Dennoch sind in praktischen Anwendungen die bekannten Algorithmen für diese Probleme häufig nur sehr eingeschränkt anwendbar. Ein Grund hierfür ist, dass die meisten bekannten Fluss- und Routingalgorithmen statische Modelle betrachten, also Modelle, in denen Zeitabhängigkeit nicht oder nur unzureichend abgebildet wird. In diesem Vortrag führen wir dynamische, also zeitabhängige, Fluss- und Routingmodelle ein. Motiviert wird die Definition dieser Modelle durch verschiedene praktische Anwendungen, z.B. in der Verkehrsplanung. Im Gegensatz zu den meisten klassischen Fragestellungen auf diesem Gebiet sind die hier auftretenden Optimierungsprobleme allerdings nicht mehr optimal in Polynomialzeit lösbar. Dennoch ist es möglich, Approximationsresultate zu erzielen, von denen wir einige vorstellen werden. Eine seit langem bekannte Methode zur Modellierung dynamischer Flüsse ist das zeitexpandierte Netzwerk. Während man mit dieser Methode sehr einfach dynamische Fragestellungen auf statische zurückführen kann, hat dieser Ansatz den Nachteil, dass er extrem große Netzwerke erzeugt und daher für praktische Anwendungen in der Regel nicht verwendbar ist. Aufbauend auf diesem zeitexpandierten Netzwerk stellen wir eine implizite Zeitexpansion vor, die eine sehr kompakte Darstellung erlaubt und damit den Entwurf schneller Routingalgorithmen möglich macht. In einem Industrieprojekt zum Routing von AGVs (Automated Guided Vehicles) konnte die praktische Effizienz der so entwickelten Verfahren nachgewiesen werden.

Vor dem Fachvortrag, welcher um 17.15 Uhr beginnt, findet noch ein Lehrvortrag von 16.30 - 17.00 Uhr mit dem Thema ``Färbung planarer Graphen`` statt.

Prof. Dr. Eckehard Köhler

TU Cottbus