User Tools

Site Tools


teaching:ss20:pg-ae

Projektgruppe: Algorithm Engineering

Aktuelles

Schicken Sie bei Interesse oder Fragen bitte eine Mail an christine.dahn [at] cs.uni-bonn.de, um eine Einladung zur Vorbesprechung zu erhalten.

  • Die Vorbesprechung findet am Donnerstag, 23.04.2020 von 12-14 online statt.
  • Die regelmäßigen Treffen werden wöchentlich donnerstags von 12-14 ebenfalls online stattfinden.
  • Die Veranstaltung wird komplett online stattfinden.
  • Die Anmeldung in Basis ist nur noch bis zum 30.04.2020 möglich.
Material eCampus, GitLab
Modulhandbuch BA-INF 051
Prüfungsanmeldung Basis (bis 30.04.2020)
Veranstalter Christine Dahn, Prof. Dr. Petra Mutzel

Inhalt

In diesem Semester werden wir uns mit dem Max Cut Problem beschäftigen. Insbesondere wollen wir bestehende Algorithmen analysieren und durch Parallelisierung beschleunigen. Dafür werden wir die Algorithmen implementieren sowie gegeneinander und gegen bekannte Max Cut Implementierungen benchmarken. Als Spezialfall werden wir planare Graphen oder dünne Graphen betrachten, da für diese Polynomilazeit Algorithmen existieren.

Beim Max Cut Problem soll die Kontenmenge eines Graphen in zwei Mengen partitioniert werden, sodass die Summe der Kantengewichte bzw. die Anzahl der Kanten zwischen diesen beiden Partitionen maximiert wird. Für planare Graphen lässt sich das Max Cut Problem in polynomieller Zeit lösen. Der aktuell schnellste Algorithmus hat eine Laufzeit von O(n^{3/2} log n) [1].

Algorithm Engineering beinhaltet den Entwurf, die theoretische Analyse, die praktische Realisierung, sowie die experimentelle Evaluierung von Algorithmen. Das Gebiet ist innerhalb der Algorithmik angesiedelt und versucht die Lücke zwischen Theorie und Praxis zu schließen. Dabei spielen reale Anwendungsszenarien oft eine wichtige Rolle, indem z.B. die besonderen Umstände der speziellen jeweiligen Anwendungen bereits bei der Problemmodellierung oder beim Algorithmendesign mitbedacht werden. Oft kann man die jeweiligen speziellen Struktureigenschaften der gegebenen Problemklassen algorithmisch ausnutzen. Diese PG behandelt ausgewählte Themen aus dem Bereich des Algorithm Engineering.

Organisation

Wenn Sie Interesse an der Projektgruppe haben, melden Sie sich bitte vorab per Mail bei christine.dahn [at] cs.uni-bonn.de. Wir schicken Ihnen dann den Einladungslink zur Vorbesprechung.

Die Veranstaltung wird komplett online stattfinden. ​Für die digitalen Treffen werden wir ein Webkonferenz System (voraussichtlich Zoom oder BBB) nutzen. Melden sie sich bei Christine Dahn, um die Einladung zur Video-Konferenz zu erhalten.

Die wöchentlichen Treffen finden donnerstags von 12-14 Uhr statt.

Terminplan

Hier finden Sie den aktuellen Terminplan für den Verlauf der Projektgruppe. Er wird im Laufe des Semesters regelmäßig aktuallisiert.

VL-Woche KW Datum
1 17 23.04.2020 Vorbesprechung + Start Literaturphase
2 18 30.04.2020 Vortragskonzept vorstellen + Fragen klären (Ende Anmeldefrist in Basis)
3 19 07.05.2020 Kurzvorträge Teil 1
4 20 14.05.2020 Kurzvorträge Teil 2
6 22 28.05.2020 Header Dateien besprechen
7 23 04.06.2020 Zwischenstand MaxCut Implementierung besprechen
8 24 10.06.2020 Zwischenstand MaxCut Implementierung besprechen
9 25 18.06.2020 Abschluss MaxCut Implementierung besprechen
10 26 25.06.2020 Preprocessing Implementierung besprechen
11 27 02.07.2020 Vortrag zu Evaluationskapiteln
12 28 09.07.2020 Vortrag zu Evaluationskapiteln + Preprocessing Implementierung besprechen
13 29 16.07.2020 geplante Tests besprechen
31 27.07.2020 Abgabe Struktur des Abschlussvortrags
31 31.07.2020 Abgabe Folien des Abschlussvortrags für Feedback
32 05.08.2020 Abgabe Folien des Abschlussvortrags für Feedback
33 07.08.2020 Abgabe finaler Folien des Abschlussvortrags
33 12.08.2020 Abschlussvortrag + Abgabe Abschlussbericht für Feedback
35 27.08.2020 Abgabe finaler Abschlussbericht

Hinweise und Vorlagen

Die verlinkten Hinweise und Vorlagen sind momentan noch auf englich.

Abschlussvortrag

Der Abschlussvortrag sollte 40-45 Minuten lang sein (mind. 20 Minuten pro Person).

In dem Vortrag soll kurz auf die verwendeten Algorithmen (max. 5 Minuten pro Person) eingegangen werden. Im Anschluss solltet ihr kurz eure Auswahl an Testdaten und das Testsetting erläutern. Der Hauptteil des Vortrags (ca die Hälfte) sollte der Auswertung eurer Testergebnisse gewidmet sein (incl anschaulicher Grafiken). Der Vortrag schließt mit einer Zusammenfassung eurer Erkenntnisse sowie einer Liste an “offenen Problemen”, die ihr zeitlich nicht mehr geschafft habt, die aber interessant wären noch untersucht oder umgesetzt zu werden.

Durch die zeitliche Beschränkung werdet ihr im Vortrag vermutlich nicht alle Ergebnisse ausführlich vorstellen können. Beschränkt euch also auf die wichtigsten Aspekte. In der Ausarbeitung sollten dann alle Ergebnisse vorgestellt werden.

Ausarbeitung

Die Ausarbeitung soll mindestens 20 Seiten (mind. 10 Seiten pro Person) umfassen und soll mit LaTeX verfasst werden. Um kenntlich zu machen wer welchen Teil geschrieben hat, schreibt bitte neben jeden Absatz den Namen des Verfassers, ggf. mehrere, wenn ihr z.B. an der Einleitung oder am Fazit zusammen geschrieben habt.

In der Strukturierung könnt ihr euch an dem Vortrag orientieren, wobei die Ausarbeitung ausfühlicher sein sollte als der Vortrag. In der Ausarbeitung sollten z.B. der Grundlagenteil (zu Definitionen und den verwendeten Algotihmen) und die Auswertung inhaltlich ausführlicher und deteilierter sein als im Vortrag. Insbesondere solltet ihr die Ergebnisse, die ihr im Vortrag aus Zeitgründen nicht vorstellen konntet, in die Ausarbeitung aufnehmen. Lange Tabellen oder große Grafiken, die den Textfluss stören, können in den Anhang verschoben werden.

Literatur

Hier finden Sie die Literatur, die wir in der PG verwenden werden, sowie weiterführende Literatur zum Thema Max Cut. Die Liste wird laufend aktualisiert.

Ein Teil der Litaratur ist nur aus dem Uninetz (kostenlos) zugänglich. Eine Anleitung wie sie sich per VPN oder SSH ins Uninetz einloggen können, finden sie auf den Seiten der GSG.

  1. Liers, Frauke, and Gregor Pardella: "Partitioning planar graphs: a fast combinatorial approach for max-cut." Computational Optimization and Applications 51.1: 323-344 (2012).
  2. Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, and Darren Strash: "Engineering Kernelization for Maximum Cut." ALENEX 2020: 27-41.
  3. Dunning, Iain, Swati Gupta, and John Silberholz. "What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO." INFORMS Journal on Computing 30.3 (2018): 608-624.
  4. Lipton, Richard J., and Robert Endre Tarjan: "A separator theorem for planar graphs." SIAM Journal on Applied Mathematics 36.2: 177-189 (1979).
  5. Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, and Alexander Nover: "Maximum Cut Parameterized by Crossing Number." Journal on Graph Algorithms and Applications 24(3): 155-170 (2020).

Dozentinnen: Mutzel, Dahn

teaching/ss20/pg-ae.txt · Last modified: 2020/08/06 12:08 by christine.dahn

Page Tools