Summer 2024
New Shortest Path Algorithms
Class hours: Mondays 14:15-15:45. Approval talks: 16:15-17:45
Slides from the plannng meeting with the list of talks
| Number | Approval Talk | Talk | Name | Topic | Mentoring |
|---|---|---|---|---|---|
| 1 | 8.4.2024 | 22.4.2024 | Edgar Perner | [BNW, Sections 2,3,A,B] | Josefine Foos |
| 2 | 15.4.2024 | 29.4.2024 | Leonard Weismantel | [BNW, Sections 6, D] | Stefan Rabenstein |
| 3 | 22.4.2024 | 6.5.2024 | Svenja Matthes | [BNW, Section 4] | Josefine Foos |
| 4 | 29.4.2024 | 13.5.2024 | Lucia Krajčoviechová | [BNW, Sections 5, C] | Benjamin Rockel |
| 5 | 6.5.2024 | 27.5.2024 | Alberto Wolff Martinez | [F, Sections 2, 3.1, 7] | Martin Drees |
| 6 | 13.5.2024 | 3.6.2024 | Lenny Schmitz | [F, Sections 3.2, 4] | Martin Drees |
| 7 | 27.5.2024 | 10.6.2024 | Jonas Handwerker | [F, Section 3.3, 6, 3.4] | Jannis Blauth |
| 8 | 3.6.2024 | 17.6.2024 | Paul Paschmanns | [F, Section 5, 3.5] | Luise Puhlmann |
| 9 | 10.6.2024 | 24.6.2024 | Carola Ley | [CW] | Susanne Armbruster |
| 10 | 17.6.2024 | 1.7.2024 | Henri Nikoleit | [ADFGW] | Antonia Ellerbrock |
| 11 | 24.6.2024 | 8.7.2024 | Lorenzo Conti | [CI] | Susanne Armbruster |
| 12 | 1.7.2024 | 15.7.2024 | Henri Saal | [FS] | Antonia Ellerbrock |
References:
- [BNW] Negative-weight single-source shortest paths in near-linear time (Bernstein, Nanongkai, Wulff-Nilsen): arXiv:2203.03456
- [F] Single-source shortest paths with negative real weights in Õ(mn^(8/9)) time (Fineman): arXiv:2311.02520
- [CW] Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky (Chan, Williams): ACM TALG 17 (2020), Article 2
- [ADFGW] Highway Dimension and Provably Efficient Shortest Path Algorithms (Abraham, Delling, Fiat, Goldberg, Werneck), https://dl.acm.org/doi/pdf/10.1145/2985473
- [CI] Distances and shortest paths on graphsof bounded highway dimension:simple, fast, dynamic (Collette, Iacono), https://arxiv.org/pdf/2312.04235.pdf
- [FS] Dijkstra's algorithm with predictions to solve the single-source many-targetsshortest-path problem (Feijen, Schäfer): arXiv:2112.11927
- 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.
All discrete mathematics lecturers