User Tools
Sidebar
Table of Contents
Projektgruppe: Algorithm Engineering (Heuristiken für Max Cut)
Aktuelles
Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte bis zum 5.4.22 eine unverbindliche formlose Anmeldung per Email an Christine Dahn, damit wir die zu erwartende Teilnehmerzahl abschätzen können. Da die Teilnehmerzahl begrenzt ist, werden die Plätze nach Eingang der Emails vergeben. Die Anmeldung per Mail ist unverbindlich. Eine verbindliche Anmeldung erfolgt nach der Vorbesprechung spätestens jedoch bis zum 8.4.22 14:00 per Mail.
| Material | eCampus und git |
|---|---|
| Modulhandbuch | BA-INF 051 |
| BASIS | BASIS |
| Formale Anmeldung | bis zum 30.04.22 auf BASIS |
| Veranstalter | Prof. Dr. Petra Mutzel, Christine Dahn |
Termine
| Termin | Wann | Wo |
|---|---|---|
| Vorbesprechung | 6.4.22 um 10:15-11:00 | Raum 2.050 (Informatik Gebäude) |
| wöchentliche Besprechung | mittwochs um 10:15-11:45 | Raum 2.074 (Informatik Gebäude) |
Direkt im Anschluss an die Vorbesprechung am 6.4. findet die Vorbesprechung der PG Graphalgorithmen statt. Sie können an beiden Vorbesprechungen teilnehmen und sich im Anschluss entscheiden an welcher PG Sie teilnehmen wollen. Sollten Sie Interesse an beiden PGs haben, schreiben Sie bitte beiden Betreuern eine Email.
Inhalt
In diesem Semester beschäftigen wir uns in der PG Algorithm Engineering mit dem Max Cut Problem (dt. maximaler Schnitt). Ein Schnitt in einem Graphen wird definiert durch eine Partition der Knoten. Alle Kanten, die zwischen den beiden Partitionen verlaufen, sind im Schnitt enthalten. Das Max Cut Problem sucht einen Schnitt mit maximalem Gewicht, d.h. das aufsummierte Kantengewicht der Schnittkanten soll maximiert werden. Das Max Cut Problem ist NP-vollständig. Daher beschäftigen wir uns im Rahmen dieser PG mit Max Cut Heuristiken.
Ziel der Projektgruppe Algorithm Engineering ist es, ein erweitertes Verständnis für speicher- und laufzeiteffiziente Implementierung, die Durchführung von algorithmischen Experimenten, sowie die Interpretation der Ergebnisse solcher zu vermitteln.
Voraussetzung: Kenntnisse der Vorlesung Graphenalgorithmen.
Sonstiges
Als Hauptartikel verwenden wir:
Kahruman, S., Kolotoglu, E., Butenko, S., & Hicks, I. V. (2007). On greedy construction heuristics for the MAX-CUT problem. International Journal of Computational Science and Engineering, 3(3), 211-218. zum Artikel
Der folgende Artikel gibt eine gute Übersicht darüber wie man Heuristiken untereinader vergleichen sollte:
Dunning, I., Gupta, S., & Silberholz, J. (2018). What works best when? A systematic evaluation of heuristics for Max-Cut and QUBO. INFORMS Journal on Computing, 30(3), 608-624. zum Artikel
Nutzen sie für die weitere Literaturrecherche google scholar, DBLP oder ArXiV.
Links
hilfreiche Tutorials zu diversen Themen (git, linux, ssh,...)
DozentInnen: Mutzel, Dahn