Ein erweitertes kontinuierliches Zeitmodell für dynamische Netzwerkflüsse

• Applicant: Professor Dr. Martin Skutella
• Subject Area: Mathematics
• Term: from 2009 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 162779298

Dynamische Netzwerkflüsse stellen eine interessante Verallgemeinerung statischer Netzwerkflüsse dar. Im Gegensatz zu letzteren beinhalten sie eine zusätzliche zeitliche Dimension, mit der die Entwicklung des Flusses im Netzwerk über die Zeit modelliert wird. In der Literatur haben sich zwei grundlegend verschiedene Varianten dynamischer Flüsse etabliert, die sich hauptsächlich im gewählten Zeitmodell unterscheiden. Im diskreten Zeitmodell ist die Zeit in Einheitsintervalle partitioniert und der Fluss wird Paketweise zu diskreten Zeitpunkten über Kanten des Netzwerks geschickt. Das andere Modell fasst die Zeit als Kontinuum auf und beschreibt den Fluss mit Hilfe von Flussraten auf den Kanten des Netzwerks. Für die Lösung von Anwendungsproblemen kommt fast nur das diskrete Zeitmodell in Frage. Im Gegensatz dazu bietet das kontinuierliche Zeitmodell die, aus theoretischer Sicht, spannenderen mathematischen Herausforderungen. Das Hauptziel dieses Projekts besteht darin, das kontinuierliche Zeitmodell um die Möglichkeit zeitlich diskreter Entscheidungen zu erweitern, so dass es eine beliebige Kombination diskreter und kontinuierlicher Netzwerkflüsse beschreiben kann. Wir möchten strukturelle Erkenntnisse gewinnen, darauf basierend algorithmische Lösungsansätze entwickeln und so die Theorie der Netzwerkflüsse vorantreiben. Der Brückenschlag zwischen diskreten und kontinuierlichen Flüssen soll durch eine innovative Kombination von Techniken aus der Algorithmischen Diskreten Mathematik und der Maßtheorie unter Einbeziehung der Funktionalanalysis gelingen.

• DFG Programme: Research Grants