direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Seminar: What are the fastest Network Flow algorithms on modern hardware?

VL-No: 3236 L 411 

Verantwortlicher: Prof. Dr. Thorsten Koch

Thema

Netzwerkflussprobleme wie das Maximal-Flussproblem und im Besonderen das Minimal-Kosten-Flussproblem (engl. Min-Cost-Flow / MCF) gehören zur Klasse der effizient lösbaren Optimierungsprobleme. Die Größe der mit ihnen bearbeiteten Netzwerke ist in den letzten Jahren deutlich angestiegen. Graphen mit Milliarden von Kanten sind üblich, so beispielsweise riesige Supply-Chain-Netzwerke oder Graphen aus sozialen Netzwerken. Auf der anderen Seite hat sich auch die Hardwarelandschaft deutlich verändert: multi-core CPUs, GPUs, FPGAs, Vector- und Streaming-Accelerators werden zum Standard. In diesem Seminar beschäftigen wir uns mit dem Stand der Dinge bei Netzwerkflussalgorithmen auf großen Netzwerken unter Zuhilfenahme neuester Hardware. Einige dieser Algorithmen sind relativ einfach und es existieren  verschiedene open source Implementierungen.

Termine

Das Seminar wird Online durchgeführt werden.

Einschreiben per E-Mail an: (Sekretariat, Frau Schulz).

Die Termine werden festgelegt, sobald die Situation bzgl. des Semesters klarer ist.

Den Angemeldeten Teilnehmern werden Einladungen für Zoom Meetings geschickt.

1. Treffen (Verteilung der Themen): TBA

2. Treffen (Kurze Präsentation der Themen): TBA

3. bis n-tes Treffen (Seminarpräsentationen): Termine werden beim ersten oder zweiten Treffen festgelegt.

Voraussetzungen

ADM I oder Kenntnisse im Gebiet Netzwerkflussalgorithmen. Angemessene Programmierkenntnisse

Literatur

Ford, Fulkerson: Flows in Networks, Princeton University Press, 1962
Bertsekas: Linear Network Optimization, MIT Press, 1991
Ahuja, Magnati, Orlin: Network Flows, Prentice Hall, 1993
Williamson: Network Flow Algorithms, Cambridge University Press, 2019

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.