This summer school on shortest paths will span theory, practice, and applications in optimization problems. We will cover single source and all pairs shortest paths in directed and undirected graphs; with exact and approximate solutions; combinatorial techniques, the use of matrix multiplication, and exploiting integer weights; fast generation of distance oracles; dynamic versions where distances are quickly recomputed when the graph updated; and various NP-hard variants of shortest path problems. Finally, we will give an overview on how shortest paths are used as subproblems in other combinatorial optimization problems.
The summer school will be held at DIKU, University of Copenhagen on July 4-8, 2005. State-of-the-art lectures will be given by the foremost researchers in the field, ensuring a proper balance between algorithms and optimization. The lectures will be supplemented by exercises and discussions.
The next DIMACS implementation challenge will be on shortest paths. The summer school is expected to generate interesting projects on meeting this challenge.
The school takes place in Auditorium 1, Universitetspaken 13, Copenhagen. The following map shows the location: Map. Registration takes place Monday, July 4, from 9.00 to 9.45.
From downtown Copenhagen you may take bus 42, 185, S150 (from Nørreport) or bus 15 (from Østerport).
We recommend the following hotels:
Last Update: June 24, 2005 by David Pisinger/ Martin Zachariasen.