Bachelor/Master-Seminar: Kürzeste-Wege-Algorithmen

Wintersemester 2013/14

Prof. Dr. Ralf Borndörfer Dr. Thomas Schlechte Dr. Marika Karbstein Marco Blanco

Inhalt Voraussetzungen Termine Hinweise Programm Kontakt

Inhalt

In diesem gemischten Bachleor/Master-Seminar für Studenten der FU und TU werden grundlegende und aktuelle Forschungsartikel zur Lösung des Kürzeste-Wege-Problems behandelt. Das kürzeste-Wege-Problem (Shortest Path Problem) ist ein klassisches Problem der diskreten Optimierung und theoretischen Informatik. Fundamental ist der Dijkstra-Algorithmus mit polynomialer Laufzeit (Komplexitätsklasse P). Heutzutage wird versucht, durch Preprocessingtechniken die zugrundeliegenden riesigen Graphen so zu verändern, dass anschließend kürzeste Wege viel schneller als mit dem klassichen Dijkstra-Algorithmus gefunden werden können. Diese Algorithmen werden z.B. bei der Straßenroutenplanung intensiv verwendet. Anderseits gibt es Algorithmen, die schwierigere Varianten des Shortest Path Problems behandeln, zum Beispiel das "Resource Constrained Shortest Path" oder das kürzeste Wege Problem mit verbotenen Subpfaden. In diesem Seminar werden zentrale Artikel der kombinatorischen Optimierung behandelt, die starken Einfluss auf die aktuelle Forschung und Entwicklung von kürzeste-Wege-Algorithmen haben.

Voraussetzungen

Grundkenntnisse in Graphen- und Netzwerkalgorithmen sowie kombinatorischer Optimierung. Für einige fortgeschrittene Themen sind Kenntnisse in linearer und ganzzahliger Optimierung notwendig.

Termine

Ein Termin mit Kurzvorträgen von jeweils 5 Minuten Dauer findet voraussichtlich statt am

Donnerstag, dem 12. Dezember 2013, ab 14:00 Uhr im Hörsaal R 2005 am Konrad-Zuse-Zentrum.

Die Folien der Vorträge und die Ausarbeitung sind bis zum

Mittwoch, dem 5. Februar 2013 um 23:59 Uhr per E-Mail an blanco

zib.de und schlechte

zib.de einzureichen.

Das Seminar wird als Blockseminar am

Donnerstag/Freitag, dem 13./14.02.2013 im Hörsaal R 2005 am Konrad-Zuse-Zentrum durchgeführt.

Hinweise zu den Vorträgen

Richtlinien für die Vortragsgestaltung und die Scheinvergabe:

Die wesentliche Leistung ist ein Vortrag von ca. 60 Minuten über das zugeteilte Thema. Im Vortrag sollen in verständlicher Form wichtige Ergebnisse des (für den Vortrag zentralen) Artikels vorgestellt werden. Ausgewählte Beweise sollen erklärt werden. Anwesenheit bei allen Vorträgen ist Pflicht! Bei Konflikte (z.B. Prüfungen oder Vorlesungen) muss der Betreuer im Voraus informiert werden.
Die Vortragsform und -medien kann jeder frei wählen. Als Vortragsmedien stehen Tafel, Overhead-Projektor und Beamer zur Verfügung. Bei einem Beamervortrag sind die Folien eine Woche vor dem Vortrag einzureichen.
Eine Woche vor dem Vortragstermin ist von den Vortragenden eine etwa 5-seitige Ausarbeitung zum Thema vorzulegen. Diese wird an alle Seminarteilnehmerinnen und Seminarteilnehmer verteilt. In dieser Ausarbeitung sollen wesentliche Definitionen und Ergebnisse zusammengefasst werden. Die Ausarbeitung soll in "Publikationsqualität" vorliegen. Es wird empfohlen, die Ausarbeitung mit Hilfe von LaTeX zu schreiben. Für LaTeX-Unkundige ist dies vielleicht ein guter Zeitpunkt, sich LaTeX anzueignen, da man im mathematischen Leben kaum darum herumkommt. (Empfehlenswerte Literatur für Einsteiger ist der erste Band der LaTeX-Serie von Helmut Kopka, erschienen bei Addison-Wesley.)

Bei der Literatursuche sind folgende Links nützlich:

Mathematische Artikel: Zentralblatt
Mathematische Webseiten: MathSearch
Mathematische und informatische Abstracts/Bibliographie: CiteSeer
Informatische Artikel/Bibliographie: ACM Portal
Wissenschaftliches Googlen: GoogleScholar

Programm

Donnerstag, 13.02.2014

9:00
Heide Hoppmann: Finding the k shortest paths
Markus Penner: Computing the K Shortest Paths: A New Algorithm and an Experimental Comparison
Alexander Hopp: Shortest paths avoiding forbidden subpaths
Christoph Spiegel: An analysis of stochastic shortest-path problems
Mittagspause

14:00
Gregor Lagodzinski: Contraction hierarchies
Ricardo Euler: Bidirectional core-based routing in dynamic time-dependent road networks
Kaffeepause
Theresa Thunig: Time-Dependent SHARC Routing
Fabian Mett: Hub label compression

Freitag, 14.02.2014

10:00
Christoph Spenke: On an exact method for the constrained shortest path problem
Alexander Tesch: Dynamic graph generation for the shortest path problem in time expanded networks
Arno Ulbricht: The Fixed-Charge Shortest-Path Problem
Mittagspause

14:00
Stanley Schade: Undirected Single Source Shortest Paths with Positive Integer Weights in Linear Time
Jakob Witzig: Shortest-path and minimum delay algorithms in networks with time-dependent edge-length
Kaffeepause
Julia Kern: Alternative Routes in Road Networks
Philipp Donner: Finding Time-Dependent Shortest Paths over Large Graphs

Kontakt

	Sprechstunde	Raum	Telefon	email
Prof. Dr. Ralf Borndörfer	n.V.	ZIB	84185-243	borndoerferzib.de
Thomas Schlechte	n.V.	ZIB	84185-317	schlechtezib.de
Marika Karbstein	n.V.	ZIB	84185-294	karbsteinzib.de
Marco Blanco	n.V.	ZIB	84185-153	blancozib.de

Zuletzt aktualisiert: 25. September 2013