Parametrisierte Algorithmik in der Computational Sustainability (PACS)

• Antragsteller: Dr. Till Fluschnik
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 522475669

Ziel der Computational Sustainability ist das Identifizieren, Formulieren und Lösen von Berechnungsproblemen, die rund um die Sicherung der Koexistenz von Menschheit und Biosphäre auftreten. Der Beitrag der Theoretischen Informatik, insbesondere der Algorithmik und Komplexitätstheorie, ist bisher eher beschränkt jedoch vielversprechend. Die typischerweise berechnungsschweren Probleme der Computational Sustainability und ihre anwendungsnahen Daten sind sehr vielseitig. Wir wollen den Weg bereiten für eine systematische Anwendung der parametrisierten Algorithmik auf ausgewählte berechnungsintensive diskrete und kombinatorische Probleme der Computational Sustainability mit dem Ziel, optimale Lösungen im Sinne von exakten Algorithmen zu finden. Vielen natürlichen Problemen in diesem Kontext wohnt (explizit oder implizit) eine spezifische Struktur inne, die durch eine entsprechende Parametrisierung eingefangen und dann in parametrisierten Algorithmen genutzt werden kann. Hierzu zählt insbesondere die effiziente und effektive Datenreduktion. Schaut man sich die Erfolgsgeschichte der parametrisierten Algorithmik in verschiedenen Anwendungsgebieten wie der Bioinformatik oder der Sozialwahltheorie an, so versprechen Methoden und Werkzeuge der parametrisierten Algorithmik viel zur Lösung relevanter Probleme der Computational Sustainability beizutragen. Diese Probleme können aus algorithmischer Sicht in verschiedenen "Reifegraden" erscheinen. In dem einen Extrem ist das unterliegende Berechnungsproblem bisher unbekannt und wird von uns erst identifiziert werden. In dem anderen Extrem liegt bereits eine mathematische Modellierung vor und es steht lediglich die Betrachtung mittels parametrisierter Algorithmik aus. Unsere Arbeit wird sich in diesem gesamten Spektrum bewegen. Zum Anfang haben wir bereits Probleme aus den Bereichen Anpassung an "Extremwetterereignisse", "Biodiversität", "Öffentlicher Personennahverkehr" und "Gemeinschaftliche Nutzung von Beförderungsmitteln" identifiziert und modelliert.

• DFG-Verfahren: Sachbeihilfen