BA-INF 051

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.

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.

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.

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

Die verlinkten Hinweise und Vorlagen sind momentan noch auf englich.

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.

• Leitfaden zum Erstellen von Folien (engl)
• Leitfaden zu Literaturangaben (engl)
• "So hälst du einen guten Vortrag" YouTube-Video von Dr. Mai Thi Nguyen-Kim

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.

• LaTeX Vorlagen (engl)
• Leitfaden zu Literaturangaben (engl)

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}