Table of Contents

Seminar Algorithm Engineering (WiSe 2015/2016)

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 vielversprechende 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 praxisrelevante 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. ParetoPrep: Fast computation of Path Skylines Queries Shekelyan, Jossé, Schubert CoRR 2014 Jan Goclik Fritz Bökler
2. Approximate Graph Mining with Label Costs Anchuri, Zaki, Barkol, Golan, Shamy SIGKDD 2013 Erik Thordsen Till Schaefer
3. Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm Baumstark, Blelloch, Shun ESA 2015 Marcel Bargull Andre Droschinsky
4. Fast approximation of betweenness centrality through sampling Riondato, Kornaropoulos WSDM 2014 David Losch Christopher Morris
5. Random Features for Large-Scale Kernel Machines Rahimi, Recht NIPS 2007 Tim Schendekehl Christopher Morris
6. Thinning out Steiner trees: a node-based model for uniform edge costs Fischetti, Leitner, Ljubic, Luipersbeck, Monaci, Resch, Salvagnin, Sinnl 11th DIMACS Implementation Challenge: Steiner trees Shabnam Tabatabaian Bernd Zey
7. Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance Romano, Bailey, Nguyen, Verspoor ICML 2014 Lutz Oettershagen Till Schaefer
8. Computing Classic Closeness Centrality, at Scale Cohen, Delling, Pajor, Werneck ACM Conference on Social Networks 2014 Patrik Elfert Petra Mutzel
9. Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search Goldberg, Hed, Kaplan, Kohli, Tarjan, Werneck ESA 2015 Christian Everke Denis Kurz
10. Public Transit Labeling Delling, Dibbelt, Pajor, Werneck SEA 2015 Kai Sauerwald Denis Kurz

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

Die Vorträge werden am 16./17.02.2016 im Raum 202, OH14 gehalten.

Dienstag, 16.02.2016 Mittwoch, 17.02.2016
9:30-10:30 Approximate Graph Mining with Label Costs
Erik Thordsen
10:30-11:30 Efficient Implementation of a Synchronous
Parallel Push-Relabel Algorithm

Marcel Bargull
Standardized Mutual Information for Clustering Comparisons:
One Step Further in Adjustment for Chance

Lutz Oettershagen
11:30-12:30 Faster and More Dynamic Maximum Flow
by Incremental Breadth-First Search

Christian Everke
Random Features for Large-Scale Kernel Machines
Tim Schendekehl
(Mittagspause) (Mittagspause)
13:30-14:30 ParetoPrep: Fast Computation of Path Skylines Queries
Jan Goclik
Computing Classic Closeness Centrality, at Scale
Patrik Elfert
14:30-15:30 Public Transit Labeling
Kai Sauerwald
Fast Approximation of Betweenness Centrality
through Sampling

David Losch
15:30-16:30 Thinning out Steiner trees: A Node-Based Model
for Uniform Edge Costs

Shabnam Tabatabaian

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt per E-Mail an Denis Kurz bis zum Montag, den 19.10.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 TeilnehmerInnen Zeit, eine Ausarbeitung zu schreiben und einen Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben. Die SeminarteilnehmerInnen können sich bei organisatorischen und inhaltlichen Fragen jederzeit an den zugeordneten Betreuer wenden.

Es soll zunächst ein Ausarbeitungskonzept von ca. 1-2 Seiten erstellt und mit dem Betreuer besprochen werden. Dieses Konzept sollte eine Gliederung der späteren Ausarbeitung umfassen sowie Stichpunkte, welche Themen in den einzelnen Abschnitten behandelt und welche weiteren Quellen verwendet werden. Das Konzept wird besprochen, bevor mit der Ausarbeitung begonnen wird; spätestens zum unten angegebenen Termin.

Die schriftlichen Ausarbeitung (Vorlage) umfasst 15-20 Seiten und muss mit LaTeX erstellt werden. Dazu muss eventuell eine Stoffauswahl getroffen werden, falls das zu bearbeitende Paper zu umfangreich ist. Die Ausarbeitung sollte inhaltlich mit dem späteren Vortrag übereinstimmen. Falls zur Bearbeitung weitere Quellen nötig sind, sollen diese im nötigen Umfang ebenfalls in der Ausarbeitung aufgearbeitet werden. Eine kritische Auseinandersetzung mit allen verwendeten Quellen, vor allem aber dem zugeordneten Paper ist ausdrücklich gewünscht. Die Ausarbeitung ist Voraussetzung für den Vortrag.

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 führen zum Nicht-Bestehen.

Alle Teilnehmer halten im Rahmen eines Blockseminars kurz nach Ende der Vorlesungszeit einen 45-minütigen Vortrag über das festgelegte Thema. Im Anschluss an jeden Vortrag 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!

Termine

Vorbesprechung und Themenvergabe: Dienstag, 20.10.2015, 14:00 Uhr (s.t.) (OH14, Raum 202)

Weitere Termine:

Ereignis Termin
Abgabe des Ausarbeitungskonzepts 23.11.2015
Abgabe der Ausarbeitung 11.01.2016
Abgabe der Ausarbeitung (Final) 25.01.2016
Abgabe der Präsentationsfolien (Aufbau) 01.02.2016
Abgabe der Präsentationsfolien (Final) 08.02.2016
Vorträge Dienstag, 16.02.2016
Mittwoch, 17.02.2016
OH 14, Raum 202

Ansprechpartner

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