Graduate Seminar on Discrete Optimization (S4C1)
Summer 2024
New Shortest Path Algorithms
Class hours: Mondays 14:1515:45. Approval talks: 16:1517: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] Negativeweight singlesource shortest paths in nearlinear time
(Bernstein, Nanongkai, WulffNilsen): arXiv:2203.03456

[F] Singlesource shortest paths with negative real weights in Õ(mn^(8/9)) time
(Fineman): arXiv:2311.02520

[CW] Deterministic APSP, orthogonal vectors, and more: quickly derandomizing RazborovSmolensky
(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 singlesource manytargetsshortestpath 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