Program for Summer School on Shortest Paths (PATH05)
Program for Summer School on Shortest Paths
| Monday, July 4 | |
| 9.00 - 9.45 | Registration (Auditorium 1, The August Krogh Building, Universitetsparken 13, DK-2100 Copenhagen) |
| 9.45 - 10.00 | David Pisinger, Mikkel Thorup, Thomas Hildebrandt: Welcome |
| 10.00 - 12.00 |
Andrew Goldberg: Single source shortest paths (SSSP): the scanning method, arbitrary arc lengths, negative cycle detection. Bellman-Ford and scaling algorithms. Variants and practical improvements of the Bellman-Ford algorithm. [pdf] |
| 12.00 - 13.00 | Lunch |
| 13.00 - 14.00 |
Natashia Boland/Irina Dumitrescu: Shortest paths and optimization: Linear programming formulations, problem variants, applications in optimization. [pdf] |
| 14.00 - 16.00 |
Exercises/discussion (Boland and Goldberg) Goldberg[pdf], Boland [pdf] (solutions)[pdf] |
| Tuesday, July 5 | |
| 9.00 - 12.00 |
Andrew Goldberg: SSSP with nonnegative arcs. Dijkstra's algorithm. Use of buckets; a linear expected time algorithm. Point-to-point (P2P) shortest paths problem, A* search. Implementation issues and experimental performance. [pdf] |
| 12.00 - 13.00 | Lunch |
| 13.00 - 15.00 | Exercises/discussion (Goldberg) [pdf] |
| 15.00 - | Excursion |
| Wednesday, July 6 | |
| 9.00 - 12.00 |
Mikkel Thorup: Best asymptotic SSSP algorithms in directed and undirected graphs with integer weights. [Part 1 pdf] [Part 2 pdf] |
| 12.00 - 13.00 | Lunch |
| 13.00 - 15.00 |
Uri Zwick: All-pairs shortest paths (APSP) with and without matrix multiplication, approximate, negative edges. [pdf] |
| 15.00 - 17.00 | Exercises/discussion (Thorup and Zwick) [pdf] |
| Thursday, July 7 | |
| 9.00 - 12.00 |
Natashia Boland/Irina Dumitrescu: Constrained shortest paths: paths with resource constraints, preprocessing and the use of Lagrangian relaxation, label setting, elementary shortest paths. [pdf] |
| 12.00 - 13.00 | Lunch |
| 13.00 - 15.00 |
Pino Italiano: Fully-dynamic all-pairs shortest paths, algorithms and experiments. [pdf] |
| 15.00 - 17.00 | Exercises/discussion (Boland, Dumitrescu and Italiano). Boland, Dumitrescu (1) [pdf], Boland, Dumitrescu (2) [pdf], (Solutions) [pdf] |
| 19.00 - | Dinner |
| Friday, July 8 | |
| 9.00 - 11.00 |
Camil Demetrescu: Fully-dynamic all-pairs shortest paths, algorithms and experiments. [pdf] |
| 11.00 - 13.00 |
Uri Zwick: Distance oracles and spanners with multiplicative and additive errors. [pdf] |
| 13.00 - 14.00 | Lunch |
| 14.00 - 15.00 |
Mikkel Thorup: Dynamic shortest paths in Internet optimization. [pdf] |
| 15.00 - 17.00 | Exercises/discussion (Demetrescu, Italiano, Thorup and Zwick) (Zwick [pdf]) |