Vorlesungen Grundlagen: Algorithmen und Datenstrukturen Diskrete Wahrscheinlichkeitstheorie Effiziente Algorithmen und Datenstrukturen II Python for Fine Programmers Proseminar Geschickt Programmieren für den ICPC-Wettbewerb Hauptseminar Ferienakademie im Sarntal Lehrveranstaltungen für Doktoranden Oberseminar

Ferienakademie im Sarntal: Distance Problems in Networks - Theory and Practice

Introduction

At first sight, it might seem that with Dijkstra's algorithm all has been said about the computation of shortest paths in networks with non-negative edge weights. Looking more closely, however, one discovers a lot of unsolved theoretical and practical problems in this field. Especially with the global use of GPS based mobile devices this classical field once again becomes quite important.

In course 2, we will first cover the well-known algorithms in this field, focusing on more recent research. Besides (rather theoretical) results about spanners, distance oracles, and distance labellings, we will treat the newest developments regarding the sped up computation of shortest paths in transportation networks as they are used in modern routing planners and navigation devices.

Lecturers

The course will be held by Prof. Mayr from Technische Universität München and Prof. Funke from Universität Stuttgart. The guest lecturer, Prof. Wanka from Friedrich-Alexander-Universität Erlangen-Nürnberg, will speak about Finding Satisfying Assignments by Random Walk. The course is organized and accompanied by Stephan Ritscher from Technische Universität München.

Presentations

Each student will have 90 minutes for the presentation which can be organised quite freely. There are, among others, the following possibilities:

• interactive development of an algorithm using the white-board,
• presentation of a computer program which demonstates the method,
• slide presentation using the projector (a LaTeX template is available here).

About half of the time slot should be reserved for discussions, questions and interaction with the audience. One could, e.g., give a 45 minute slide presentation, leaving 45 minutes for questions and discussions.

Thus, in each session we will have about 2 presentations. The language for presentations is English.

You will also have to write a paper of 6-7 pages which gives an introduction into the subject of your talk on the level of the course. Please use the LaTeX template since all presentations will be compiled into one single document in the end.

After the course, all presentations and papers will be collected and made available on the course homepage. The participants will also receive a CD-ROM contatining the talks and pictures from the course. Therefore all students will have to overhaul their presentations and finish the papers until (at latest) two weeks after the seminar (15. October 2010).

Topics

An overview of speed-up techniques for shortest path computations is given by Dorothea Wagner and Thomas Willhalm. It is recommended to all students to have a look at this article before preparing the own presentation.