Table of Contents

Seminar Algorithm Engineering (WiSe 2017/2018)

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 14

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

(verlinkter) Titel Autoren Konferenz/Journal Vortrags-Zeit Teilnehmer/in Betreuer/in
1. Exact Approaches to Multilevel Vertical Orderings Chimani, Hungerländer INFORMS2013 Di 10-11:00 JJ Adalat Jabrayilov
2. An exact approach for the Vertex Coloring Problem E. Malaguti, M. Monaci, P. Toth DO2011 Di 11-12:00 JS Adalat Jabrayilov
3. Bipartite Matching with Linear Edge Weights Nevzat Onur Domanic, Chi-Kit Lam, C. Gregory Plaxton ISAAC 2016 Di 12-13:00 RH Andre Droschinsky
4. Upper and Lower Bounds for Online Routing on Delauney Triangulations Bonichon, Bose, Carufel, Perković, Renssen ESA 2015 Di 14-15:00 CD Andre Droschinsky
5. On the Power of Color Refinement V. Arvind, J. Köbler, G. Rattan, O. Verbitsky FCT 2015 Di 15-16:00 FL Christopher Morris
6. Sherali--Adams Relaxations and Indistinguishability in Counting Logics A. Atserias and E. Maneva SIAM J. Comput. MR Christopher Morris
7. Distributed Submodular Maximization Mirzasoleiman, B.; Karbasi, A.; Sarkar, R. & Krause, A. JMLR2016 Di 16-17:00 FH Till Schäfer
8. Large-scale frequent subgraph mining in MapReduce Lin, W.; Xiao, X. & Ghinita, G. ICDE2014 Mi 10-11:00 PD Till Schäfer
9. Size- and Port-Aware Horizontal Node Coordinate Assignment Ulf Rüegg, Christoph Daniel Schulze, John Julian Carstens, Reinhard von Hanxleden GD 2015 Mi 11-12:00 BW Christiane Spisla
10. Finding k Simple Shortest Paths and Cycles Udit Agarwal, Vijaya Ramachandran ISAAC 2016 DT Christiane Spisla
11. Decomposition methods for the two-stage stochastic Steiner tree problem Markus Leitner, Martin Luipersbeck, Markus Sinnl, Ivana Ljubic TR2017 t Bernd Zey
12. Subexponential parameterized algorithms for graphs of polynomial growth Dániel Marx and Marcin Pilipczuk ESA2017 t Petra Mutzel
13. Contracting a Planar Graph Efficiently Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Eva Rotenberg and Piotr Sankowski. ESA2017 FB Bernd Zey
14. Streaming Algorithms for Matching Size Estimation in Sparse Graphs Graham Cormode, Hossein Jowhari, Morteza Monemizadeh and S Muthukrishnan ESA2017 t Petra Mutzel
15. Randomized Contractions for Multiobjective Minimum Cuts Aissi Hassene, A. Ridha Mahjoub and R. Ravi ESA2017 Mi 12-13:00 SA Petra Mutzel
16. Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles Moritz Baum, Julian Dibbelt, Dorothea Wagner and Tobias Zündorf ESA2017 Mi 14-15:00 SB Bernd Zey
17. Dynamic Space Efficient Hashing Tobias Maier and Peter Sanders ESA2017 Mi 15-16:00 TT Petra Mutzel

Anmeldung und Vorbesprechung

Die Anmeldung erfolgt unter Angabe von Name, Email (TU Dortmund), Matrikelnummer und der Nummer von drei Themen (nach Priorität gereiht) per E-Mail an Adalat Jabrayilov (s. Termine). Da die Teilnehmerzahl beschränkt ist, können nur die ersten 14 Anfragen berücksichtigt werden. Eine erfolgreiche Anmeldung wird durch eine E-Mail bestätigt. Die Themenverteilung erfolgt bei der Vorbesprechung (s. Termine). Die Anmeldung ist abgeschlossen.

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

Anmeldung: bis zum 10.10.2017

Vorbesprechung und Themenvergabe: Mittwoch, 11.10.2017, 12:00 Uhr (s.t.) (OH14, Raum 202)

Weitere Termine:

Ereignis Termin
Abgabe des Ausarbeitungskonzepts 13.11.2017
Abgabe der Ausarbeitung 13.12.2017
Abgabe der Ausarbeitung (Final) 10.01.2018
Abgabe der Präsentationsfolien (Aufbau) 17.01.2018
Abgabe der Präsentationsfolien (Final) 24.01.2018
Vorträge Dienstag, 6.02.2018
Mittwoch, 7.02.2018
OH 14, Raum 202

Hinweis: Die Vorträge finden Dienstag ab 10 Uhr und Mittwoch ab 10 Uhr statt

Benotungskriterien

Kriterien der schriftlichen Ausarbeitung:

Kriterien des Vortrags:

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Adalat Jabrayilov oder Petra Mutzel.