DE EN
Menü

Graduate Seminar on Discrete Optimization (S4C1)

← Semesterübersicht

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