Graduate Seminar on Discrete Optimization (S4C1)

Summer 2023

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

In 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva gave the first algorithm for Maximum Flow and Minimum-Cost Flow with almost-linear running time. The paper can be found here: https://arxiv.org/abs/2203.00671.pdf. A talk on this topic by Rasmus Kyng can be found here: [video].

The slides from the planning meeting can be found here. The list of topics is available here.

Class hours: Mondays 14:15-15:45. Approval talks: 16:15-17:45
Number Approval Talk Talk Name Topic Mentoring
1 3.4. (14:15) 17.4. Timo Brand Potential Reduction Interior Point Method Tilmann Bihler
2 3.4. 24.4. Armin Settels Expander Decompositions Jannis Blauth
3a 2.5. (Tue), 10:15 8.5. Paula Heinz Decremental Spanners with Embedding: The Algorithm Josefine Foos
3b 24.4. 15.5. Daniel Philipp Ebert Decremental Spanners with Embedding: Implementing the Sparsification Procedure Josefine Foos
4 8.5. 22.5. Rebecca Hellmann Low Strech Spanning Trees Benjamin Klotz
5 15.5. 5.6. Malte Baumecker Link-Cut Trees Daniel Blankenburg
6 22.5. 12.6. Yannik Spitzley Data Structure Chain Daniel Blankenburg
7a 5.6. 19.6. Joes Friedrich Biburger Routing and Cycle Quality Bounds I Susanne Armbruster
7b 19.6.(12:15) 26.6. Maximilian Keßler Routing and Cycle Quality Bounds II Susanne Armbruster
8 19.6. 3.7. Laura Bülte Rebuilding Data Structure Levels Meike Neuwohner
9 26.6. 10.7. Manuel Christalla The Overall Algorithm Meike Neuwohner
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Jun.-Prof. Dr. V. Traub,
Dr. U. Brenner