Entwurf, Analyse und Implementierung von Aufzählungsalgorithmen

• Antragsteller: Dr. Martin Schirneck
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 556899211

Viele Anwendungen im Data-Mining, der Bioinformatik oder im Bereich der künstlichen Intelligenz haben nicht eine einzelne, beste Lösung. Stattdessen ist die Aufgabe eine diverse Auswahl von Optionen zu berechnen, oft müssen sogar alle überhaupt möglichen Lösungen aufgezählt werden. Die Forschung an Aufzählungsalgorithmen leidet aktuell unter einer strikten Trennung zwischen Theorie und Praxis. So wurden die Schwachstellen gegenwärtiger Aufzählungsmethoden meist bereits in der algorithmischen Literatur behandelt, die Lösungen aber nicht in der Praxis implementiert. Umgekehrt passen die mathematischen Analysen von Eingabe-Strukturen für effiziente Algorithmen nicht unbedingt zu den Instanzen, die tatsächlich in Anwendungen vorkommen. Unser Ziel ist es diese Trennung im Falle des Transversal Hypergraph Problems zu überwinden, dies ist die Aufgabe alle inklusionsminimalen Hitting-Sets eines Hypergraphens aufzuzählen. Dazu bedarf es Forschung in drei Bereichen: Zum Ersten untersuchen wir die kombinatorischen Eigenschaften von Hypergraphen aus praktischen Anwendungen. Diese weisen oft eine heterogene Gradverteilung und kleine Hitting-Sets auf. Zum Zweiten benutzen wir Methoden aus dem Algorithm Engineering, um den Einfluss von Heuristiken und unterstützenden Datenstrukturen auf die Effizienz von Aufzählungsmethoden zu analysieren. Zu guter Letzt identifizieren und lösen wir die technischen Schwierigkeiten, die aktuell noch dem Transfer theoretischer Erkenntnisse in die Praxis im Weg stehen. Die Analyse von Abhängigkeiten in relationalen Datenbanken ist dabei ein Anwendungsbereich, in dem die Ergebnisse dieses Projektes direkt einen positiven Effekt entfalten können.

• DFG-Verfahren: Sachbeihilfen