Table of Contents

Seminar Algorithm Engineering (SoSe 2015)

Veranstalterin Prof. Dr. Petra Mutzel
Modul Diplom, Master INF-MSc-102 (Informatik, Angewandte Informatik)
Veranstaltungsart Seminar
Veranstaltungsnummer 041405
Forschungsbereich Algorithmen und Komplexität
SWS 2
Max. Teilnehmer 12

Inhalt

Algorithmen und Datenstrukturen sind das Herz jeder Computeranwendung. Traditionell hat sich die Algorithmik der Methodik der Algorithmentheorie bedient: Algorithmen werden für einfache und abstrakte Problem- und Maschinenmodelle entworfen und Leistungsgarantien werden für alle möglichen Eingaben bewiesen (z.B. Worst-Case-Analyse).

Bei wachsenden Anforderungen an innovative Algorithmen ergeben sich daraus wachsende Lücken zwischen Theorie und Praxis: Reale Hardware entwickelt sich durch Parallelisierung, Speicherhierarchien, Pipelining, etc. immer weiter weg von einfachen Maschinenmodellen und reale Anwendungen werden immer komplexer. Gleichzeitig entwickelt die Algorithmentheorie auch für einfache Anwendungen immer komplexere Algorithmen, die zwar in der Theorie wichtige Ideen und Resultate liefern, aber oft auch kaum implementierbar sind. Außerdem haben reale Eingaben oft wenig mit den Worst-Case Szenarien der theoretischen Analyse zu tun. Im schlimmsten Fall werden viel versprechende algorithmische Ansätze vernachlässigt, weil eine vollständige Analyse mathematisch zu schwierig wäre.

Seit Beginn der 1990er Jahre wird deshalb eine breitere Sichtweise der Algorithmik immer wichtiger, die als Algorithm Engineering bezeichnet wird. Dabei stehen der Entwurf, die Analyse, die Implementierung und die experimentelle Bewertung von Algorithmen gleichberechtigt nebeneinander. Der gegenüber der Algorithmentheorie größere Methodenapparat, die Einbeziehung realer Hard- und Software und der engere Bezug zu realen Anwendungen verspricht realistische Algorithmen. Dadurch soll die Lücke zwischen Theorie und Praxis überbrückt und ein schnellerer Transfer von algorithmischem Wissen in Anwendungen gewährleistet werden.

In diesem Seminar beschäftigen wir uns mit ausgewählten aktuellen Veröffentlichungen aus dem Bereich des Algorithm Engineerings, die auf internationalen Konferenzen oder in Zeitschriften erschienen sind.

Themenliste

Titel Autoren Konferenz Teilnehmer Betreuer
1. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection Hüffner, Wernicke, Zichner Algorithmica 52:2 Sebastian Opriel Nils Kriege
2. Polynomial-time construction of contraction hierarchies for multi-criteria objectives Funke, Storandt ALENEX 2013 Mark Schröder Denis Kurz
3. Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling Akiba, Iwata, Kawarabayashi, Kawata ALENEX 2014 Pia Wierzoch Andre Droschinsky
4. Flow-Based Guidebook Routing Bast, Storandt ALENEX 2014 Daniel Friesel Petra Mutzel
5. PReaCH: A Fast Lightweight Reachability Index using Pruning and Contraction Hierarchies Merz, Sanders ESA (Track B) 2014 Ole Bergenholtz Andre Droschinsky
6. Robust Distance Queries on Massive Networks Delling, Goldberg, Pajor, Werneck ESA (Track B) 2014 Jan Stallmann Petra Mutzel
7. Subgraph Enumeration in Dynamic Graphs Adiga, Vullikanti, Wiggins ICDM 2013 Tobias Heinlein Nils Kriege
8. Active Density-based Clustering Mai, He, Hubig, Plant, Böhm ICDM 2013 Patrick Brandt Till Schäfer
9. Finding k Shortest Paths in Directed Graphs: A Node Classification Algorithm Feng Networks 2014 Raoul Lefmann Denis Kurz
10. Bidirectional preference-based search for multiobjective state space graph problems Galand, Ismaili, Perny, Spanjaard SoCS 2013 Tobias Marquardt Fritz Bökler

Auf alle Artikel kann aus dem Uni-Netzwerk (oder mittels VPN von zu Hause aus) zugegriffen werden.

Die Vorträge werden vom 20.-21.07.2015 im Raum 202, OH14 gehalten.

Montag, 20.07.2014 Dienstag, 21.07.2015
9:00-10:00 Fast Shortest-path Distance Queries on Road
Networks by Pruned Highway Labeling

Pia Wierzoch
PReaCH: A Fast Lightweight Reachability Index
using Pruning and Contraction Hierarchies

Ole Bergenholtz
10:00-11:00 Polynomial-time construction of contraction
hierarchies for multi-criteria objectives

Mark Schröder
Algorithm Engineering for Color-Coding with
Applications to Signaling Pathway Detection

Sebastian Opriel
11:00-12:00 Bidirectional preference-based search for
multiobjective state space graph problems

Tobias Marquardt
Subgraph Enumeration in Dynamic Graphs
Tobias Heinlein
(Pause bis 13:30 Uhr) (Pause bis 14:00 Uhr)
13:30-14:30 Flow-Based Guidebook Routing
Daniel Friesel
Active Density-based Clustering
Patrick Brandt
14:30-15:30 Robust Distance Queries on Massive Networks
Jan Stallmann
15:30-16:30 Finding k Shortest Paths in Directed Graphs:
A Node Classification Algorithm

Raoul Lefmann

Vorsicht: Der letzte Vortrag am Dienstag kann wegen einer parallel stattfindenden Klausur erst von 14:00-15:00 stattfinden.

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt per E-Mail an Denis Kurz bis zum Montag, den 06.04.2015. Da die Teilnehmerzahl beschränkt ist, können nur die ersten 12 Anfragen berücksichtigt werden. Eine erfolgreiche Anmeldung wird durch eine E-Mail bestätigt. Die Themenverteilung erfolgt bei der Vorbesprechung (Termin s. unten).

Ablauf des Seminars

Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit, die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben. Die Seminarteilnehmer besprechen sich allerdings mit ihrem zugeordneten Betreuer.

Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende der Vorlesungszeit einen 45-minütigen Vortrag über das festgelegte Thema. Im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!

Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen Ausarbeitung, welche 15-20 Seiten umfasst und mit LaTeX erstellt wird. Nach der Abgabe der Ausarbeitung besteht einmalig die Gelegenheit, die Ausarbeitung auf Grundlage des Feedbacks des Betreuers zu überarbeiten. Mangelhafte Ausarbeitungen und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Seminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen.

Vorlage für die Ausarbeitung: [.zip-Archiv]

Termine

Vorbesprechung und Themenvergabe: 09.04.2015, 15:00 Uhr (s.t.) (OH 14, Raum 202)

Weitere Termine:

Abgabe des Ausarbeitungskonzepts 01.06.2015
Abgabe der Ausarbeitung 15.06.2015
Abgabe der Ausarbeitung (Überarbeitete Version) 29.06.2015
Abgabe der Präsentationsfolien (Aufbau) 06.07.2015
Abgabe der Präsentationsfolien (Final) 13.07.2015
Vorträge Montag, 20.07.2015
Dienstag, 21.07.2015
OH 14, Raum 202

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Denis Kurz oder Petra Mutzel.