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

VL-No: 3236 L 411 

Responsible: Prof. Dr. Thorsten Koch

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.

Seminar will be conducted online.

Enrollment by E-Mail to: aschulz@math.tu-berlin.de [1] (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.

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

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