direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

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

VL-No: 3236 L 411 

Responsible: Prof. Dr. Thorsten Koch

Topic

Network Flow problems, i.e., Max-Flow and in particular Min-Cost-Flow (MCF) are a class of optimization problems that can be solved efficiently. In recent years the size of networks to consider has grown dramatically. Graphs with billions of links become daily business, e.g., huge supply-chain-networks, or graphs from social networks. On the other hand, the hardware landscape has also changed considerably: multi-core CPUs, GPUs, FPGAs, Vector- and Streaming-Accelerators are becoming common. In this seminar we will investigate the state-of-the-art in network flow algorithms on huge networks using the latest hardware. Some of the algorithms are relatively simple and different open source implementations are available.

Dates

Seminar will be conducted online.

Enrollment by E-Mail to:  (Sekretariat, Frau Schulz).

The initial dates will be announced once the situation regarding the semester is stable.

The enrolled participants will receive an invitation to a Zoom meeting by E-mail.

1. Meeting (distribution of topics): TBA

2. Meeting (Short presentation of the topics): TBA

3 to n-th. Meeting (Seminarpresentations): Will be scheduled at the 1st or 2nd meeting.

Prerequisites

ADM I, or knowledge of network flow algorithms. Reasonable programming skills

Literature

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

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.