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 |
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Jun.-Prof. Dr. V. Traub,
Dr. U. Brenner