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

VL-No: 3236 L 411 

Verantwortlicher: Prof. Dr. Thorsten Koch

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.

Das Seminar wird Online durchgeführt werden.

Einschreiben per E-Mail an: aschulz@math.tu-berlin.de [1] (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.

ADM I oder Kenntnisse im Gebiet Netzwerkflussalgorithmen. Angemessene Programmierkenntnisse

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 [2], Cambridge University Press, 2019