Summer School on Shortest Paths -
Between Algorithms and Optimization
(PATH05)

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.

Speakers

• Natashia Boland, The University of Melbourne, Australia
• Camil Demetrescu, University of Rome, Italy
• Andrew Goldberg, Microsoft Research, Silicon Valley, California
• Pino Italiano, University of Rome, Italy
• Mikkel Thorup, AT&T Labs, New Jersey
• Uri Zwick, Tel Aviv University, Israel

Program and Literature

Pictures

Getting to the Summer School

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

Registration

Hotel reservation

We recommend the following hotels:

Program and Organizing Committee

• Mikkel Thorup, AT&T Labs
• David Pisinger, University of Copenhagen
• Inge Li Gørtz, IT-University of Copenhagen
• Anna Ostlin Pagh, IT-University of Copenhagen
• Rasmus Pagh, IT-University of Copenhagen
• Martin Zachariasen, University of Copenhagen

Sponsors

Last Update: June 24, 2005 by David Pisinger/ Martin Zachariasen.