Wir freuen uns über Ihr Interesse. Wenn Sie überlegen an der Projektgruppe teilzunehmen, schreiben Sie bitte eine unverbindliche formlose Email an Daniel Faber. 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. Nahezu alle State-of-the-Art Methoden für das exakte Lösen des MWCSP basieren auf ganzzahliger linearer Optimierung (Integer Linear Programming, ILP). ILPs werden in der Praxis auch für viele andere NP-schweren Probleme eingesetzt. Im Rahmen dieser Projektgruppe werden wir uns daher mit dem exakten Lösen des MWCSP mithilfe ILPs beschäftigen. Des Weiteren werden wir effiziente Preprocessing-Algorithmen zur Reduzierung der Instanzgrößen implementieren. (Grundkenntnisse zu ILPs werden zu Beginn der Projektgruppe aufgefrischt; entweder durch uns oder in Form von Kurzvorträgen der Studierenden.)

Die Projektgruppe wird in Kooperation mit der Projektgruppe Graphenalgorithmen durchgeführt, bei der es schwerpunktmäßig um effiziente heuristische Algorithmen für das MWCSP geht.

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}