Datengetriebene parametrisierte Algorithmik von Graphmodifikationsproblemen (DAPA)

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 210010251

Probleme aus diversen Anwendungsbereichen wie Biologie, Operations Research oder Bildverarbeitung lassen sich als Graphmodifikationsprobleme in einfacher und eleganter Weise modellieren. Für einen gegebenen Graphen soll durch möglichst geringfügige Modifikationen (in erster Linie Knoten- und Kantenlöschungen und Kanteneinfügungen) seine Struktur nach gewissen Zielvorgaben geändert werden. Leider sind die meisten Graphmodifikationsprobleme NP-schwer, also keine im Allgemeinen effizienten Algorithmen zur Bestimmung einer kleinstmöglichen Menge von Modifikationsoperationen zu erwarten. Jedoch schöpft man Hoffnung für praktisch relevante, effizient lösbare Spezialfälle zum einen dadurch, dass oft nur eine geringe Anzahl Modifikationen nötig bzw. erwünscht ist, und zum anderen dadurch, dass die Eingabegraphen in der Regel aus der Anwendung heraus ausnutzbare spezielle Strukturen aufweisen. Damit lassen sich ”Problemparametrisierungen“ gewinnen, die zur Entwicklung effizienter parametrisierter Algorithmen ausgenutzt werden können. Dieser Gewinnungsprozess soll datengetrieben vonstattengehen, d. h. interessante Parametrisierungen sollen vorzugsweise aus realen Daten aus den Anwendungskontexten ”Daten-Clustering“ und ”Planning“ extrahiert werden. Dabei spielen bei DAPA neben theoretischen Analysen auch Implementierungsarbeiten und Experimente eine wesentliche Rolle.

• DFG-Verfahren: Sachbeihilfen