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: 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.
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 [2], Cambridge University Press,
2019
nfrage/parameter/de/font2/minhilfe/id/212522/?no_cache=
1&ask_mail=YrpT3wAMDxNg%2FPcR19u1EFcDNyiZHyURcTHnlr
6gtQs%2Fm0wTH8Y57g%3D%3D&ask_name=ASCHULZ