Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte eine unverbindliche formlose Email an Philip Mayer. Die Projektgruppe hat eine maximale Teilnehmer*innen Anzahl; bitte erwähnen Sie in Ihrer Mail, welche Wahlpflichtfächer in der Algorithmik Sie belegt haben und wann Sie Algorithmen und Berechnungskomplexität 1 und 2 abgeschlossen haben. Kenntnisse aus den zuletzt genannten Modulen und der Vorlesung Graphenalgorithmen werden unbedingt vorausgesetzt.

In dieser Projektgruppe werden wir uns mit algorithmischen Lösungen für Graphprobleme beschäftigen, die Anwendungen in der Systembiologie (Protein-Interaktions-Netzwerken) und der Planung von Naturschutzgebieten (Optimierung von Biotopvernetzung) besitzen.

Das Kernproblem ist das Maximum Weight Connected Subgraph Problem (MWCSP). Hierbei ist ein Graph mit (positiven und negativen) Knotengewichten gegeben, und man möchte eine Teilmenge von Knoten finden, die einen zusammenhängenden Teilgraphen mit maximalem Gesamtgewicht (Summe der Knotengewichte) induziert. Varianten davon besitzen zusätzliche Nebenbedingungen, wie z.B. Budget- oder Size-Constraints.

Das MWCSP ist NP-schwer. Im Rahmen dieser Projektgruppe werden algorithmische Ideen für Heuristiken und exaktes Preprocessing aus der Literatur implementiert, eventuell verbessert oder neu entwickelt.

Die Projektgruppe wird in Kooperation mit der Projektgruppe Algorithm Engineering durchgeführt, bei der es um die Umsetzung von exakten Verfahren mittels ganzzahliger linearer Optimierung (ILP) geht. (Grundkenntnisse zu ILPs werden zu Beginn der Projektgruppe aufgefrischt; entweder durch uns oder in Form von Kurzvorträgen der Studierenden.)

Ziel der Projektgruppe ist es, ein vertieftes Verständnis für laufzeiteffiziente Implementierung, die Durchführung algorithmischer Experimente sowie die Interpretation der entsprechenden Ergebnisse zu vermitteln.

Die benotete Prüfungsleistung der PG ist ein Vortrag am Ende der Vorlesungszeit und eine schriftliche Ausarbeitung in der die Ergebnisse wissenschaftlich präsentiert werden.

• A Guide to Experimental Algorithmics
• Guidelines for Experimental Algorithmics: A Case Study in Network Analysis
• A Theoretician’s Guide to the Experimental Analysis of Algorithms
• The Maximum Weight Connected Subgraph Problem
• Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
• Solving the Maximum-Weight Connected Subgraph Problem to Optimality
• Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
• Optimal Connected Subgraphs: Formulations and Algorithms

_{DozentInnen: Mutzel, Faber, Mayer}