Program for Summer School on Shortest Paths
(PATH05)


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])