Approximationsgrenzen der dynamischen Programmierung

• Antragsteller: Dr. Stasys Jukna
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389079104

Die dynamische Programmierung (DP) ist ein erfolgreiches algorithmisches Paradigma für die Lösung von Optimierungs- sowie Abzähl- und Entscheidungsproblemen. Die Grenzen exakter DP-Algorithmen sind derzeit relativ gut verstanden: Wir sind in der Lage, nicht-triviale untere Schranken für die Anzahl der benötigten Operationen zeigen. Der gegenwärtige Kenntnisstand zur Approximationskomplexität von DP-Algorithmen blieb aber äußerst enttäuschend: keine nicht-trivialen unteren Schranken für approximierende DP-Algorithmen waren bekannt. Während des Bewilligunszeitraumes haben wir diese Kenntnislücke geschlossen: Wir haben die ersten, sogar exponentiellen unteren Schranken auch für approximierende DP-Algorithmen bewiesen. Außerdem haben wir gezeigt, dass Randomisierung in approximierenden DP-Algorithmen nur wenig helfen kann.Unsere untere Schranken gelten für sogenannte reine DP-Algorithmen, die die Basisoperationen (min,+) oder (max,+) in ihren Rekursionsgleichungen benutzen. Vor Kurzem hat sich herausgestellt, auch dank einem von unseren gerade erzielten Resultaten, dass Subtraktion DP-Algorithmen sogar exponentiell beschleunigen kann. Das Ziel der Fortsetzung ist daher, die Ursachen dieser überraschenden Kraft der Subtraktion in der dynamischen Programmierung zu verstehen. Wir wollen dies durch den Nachweis unterer Schranken für DP-Algorithmen mit Subtraktion erreichen.

• DFG-Verfahren: Sachbeihilfen