Grenzen der dynamischen Programmierung

• Antragsteller: Professor Dr. Georg Schnitger
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2017
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 237501959

Der gegenwärtige Kenntnisstand zur dynamischen Programmierkomplexität (DP-Komplexität) algorithmischer Probleme ist äußerst enttäuschend: Das All-Pairs Shortest Path Problem ist eines von sehr wenigen nicht-trivialen Problemen, dessen DP-Komplexität angemessen verstanden ist. Die DP-Komplexität anderer Kürzeste-Wege Probleme ist ungeklärt wie auch die vermeintliche Optimalität vieler fundamentaler dynamischer Programmier-Algorithmen in Informatik und Bioinformatik. Wir treffen dieselbe trostlose Situation an, wenn mit dynamischen Programmieralgorithmen approximiert wird.Unser Ziel ist die Formulierung adäquater Modelle, die das Paradigma der dynamischen Programmierung beschreiben und der Nachweis unterer Schranken für wichtige Optimierungsprobleme in diesen Modellen. Insbesondere sollen mächtige Methoden der Booleschen Schaltkreiskomplexität sowie der Kommunikationskomplexität angewandt werden.

• DFG-Verfahren: Sachbeihilfen