Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+====== Seminar Algorithm Engineering (WiSe 2015/2016) ======
+| Veranstalterin    | [[staff:mutzel|Prof. Dr. Petra Mutzel]] |
+| Modul             | Diplom, Master [[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Master_Inf/Pflichtveranstaltungen/INF-MSc-102.pdf|INF-MSc-102 (Informatik, Angewandte Informatik)]] |
+| Veranstaltungsart | Seminar                     |
+| Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=163110&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|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. | [[http://arxiv.org/abs/1410.0205|ParetoPrep: Fast computation of Path Skylines Queries]] | Shekelyan, Jossé, Schubert | CoRR 2014 |  Jan Goclik  |  [[:staff:boekler|Fritz Bökler]]  |
+| 2. | [[http://dx.doi.org/10.1145/2487575.2487602|Approximate Graph Mining with Label Costs]] | Anchuri, Zaki, Barkol, Golan, Shamy | SIGKDD 2013 |  Erik Thordsen  |  [[:staff:Schäfer|Till Schaefer]]  |
+| 3. | [[http://arxiv.org/pdf/1507.01926.pdf|Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm]] | Baumstark, Blelloch, Shun | ESA 2015 |  Marcel Bargull  |  [[:staff:droschinsky|Andre Droschinsky]]  |
+| 4. | [[http://link.springer.com/article/10.1007%2Fs10618-015-0423-0|Fast approximation of betweenness centrality through sampling]] | Riondato, Kornaropoulos | WSDM 2014 |  David Losch  |  [[:staff:morris|Christopher Morris]]  |
+| 5. | [[http://papers.nips.cc/paper/3182-random-features-for-large-scale-kernel-machines.pdf|Random Features for Large-Scale Kernel Machines]] | Rahimi, Recht | NIPS 2007 |  Tim Schendekehl  |  [[:staff:morris|Christopher Morris]]  |
+| 6. | [[http://homepage.univie.ac.at/ivana.ljubic/research/publications/ThinningOutSteinerTrees.pdf|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  |  [[:staff:zey|Bernd Zey]]  |
+| 7. | [[http://jmlr.org/proceedings/papers/v32/romano14.html|Standardized Mutual Information for Clustering Comparisons: One Step Further in Adjustment for Chance]] | Romano, Bailey, Nguyen, Verspoor  | ICML 2014 |  Lutz Oettershagen  |  [[:staff:Schäfer|Till Schaefer]]  |
+| 8. | [[http://arxiv.org/pdf/1409.0035.pdf|Computing Classic Closeness Centrality, at Scale]] | Cohen, Delling, Pajor, Werneck | ACM Conference on Social Networks 2014 |  Patrik Elfert  |  [[:staff:mutzel|Petra Mutzel]]  |
+| 9. | [[http://dx.doi.org/10.1007/978-3-662-48350-3_52|Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search]] | Goldberg, Hed, Kaplan, Kohli, Tarjan, Werneck | ESA 2015 |  Christian Everke  |  [[:staff:kurz|Denis Kurz]]  |
+| 10. | [[http://dx.doi.org/10.1007/978-3-319-20086-6_21|Public Transit Labeling]] | Delling, Dibbelt, Pajor, Werneck | SEA 2015 |  Kai Sauerwald  |  [[:staff:kurz|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 [[staff:kurz|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** (**{{:teaching:ausarbeitung-ae2013.zip|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 [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|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 |
+===== Links =====
+  * Vorlage für die Ausarbeitung: {{:teaching:ausarbeitung-ae2013.zip|[.zip-Archiv]}}
+  * [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|Hinweise zur Foliengestaltung]]
+===== Ansprechpartner =====
+Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an [[staff:kurz|Denis Kurz]] oder [[staff:mutzel|Petra Mutzel]].

Chair 11

Teaching

Research Groups

Differences