Graduate Seminar on Discrete Optimization (S4C1)
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