Approximation limits of dynamic programming
Final Report Abstract
Die dynamische Programmierung (DP) ist ein erfolgreiches algorithmisches Paradigma für die Lösung von Optimierungs- sowie Abzähl- und Entscheidungsproblemen. Dieses algorithmische Prinzip ist so natürlich, dass man kaum hinterfragt, ob es auch optimal ist. Genau diese Frage, und zwar nicht nur für exakt lösende, sondern auch für approximierende DP-Algorithmen, haben wir gestellt und in vielen Fällen beantworten können. Dabei beschränken wir uns auf sogenannte „reine“ DP-Algorithmen, die in ihren Rekrsionsgleichungen nur grundlegende Operationen, wie Min bzw. Max, Addition oder Subtraktion, aber keine Verzweigungen benutzen. Erstens sind viele fundamentale DP-Algorithmen rein und zweitens sind unbeschränkte DP-Algorithmen zu mächtig: eine super-polynomielle untere Schranke für solche DP-Algorithmen würde das P-vs.-NP-Problem lösen. Einige Grenzen exakt lösender DP-Algorithmen waren bereits verstanden: Wir sind in der Lage, einige 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 bisher bekannt. Im Rahmen des Projekts konnten wir diese Kenntnislücke größtenteils schließen. Unter anderem haben wir die folgenden Resultate erzielt. • Zwei allgemeine Methoden zum Nachweis unterer Schranken für approximierende reine DP-Algorithmen. Angewandt auf explizite Optimierungsprobleme haben diese Methoden zu den ersten nicht-trivialen, sogar exponentiellen unteren Schranken für approximierende DP-Algorithmen geführt. • Randomisierung kann DP-Algorithmen nicht substantiell beschleunigen: in exakt lösenden Algorithmen kann die Beschleunigung höchstens quadratisch und in approximierenden Algorithmen höchstens kubisch sein. Überraschenderweise gilt dieses Resultat nicht nur für reine DP-Algorithmen, sondern auch für beliebige auf reellen Zahlen arbeitende Algorithmen, die Operationen beschränkter algebraischer Beschreibungskomplexität ausführen. • Nicht-sukzessive DP-Algorithmen können exponentiell schneller als sukzessive DP-Algorithmen sein (ein DP-Algorithmus ist sukzessiv, wenn in jeder Addition eine der Eingaben eine Variable ist; z.B. ist der Bellman-Ford-Algorithmus und viele andere sukzessiv). • Reine DP-Algorithmen können für einige Optimierungsproblemen viel schlechter als Greedy- Algorithmen sein (dass Greedy-Algorithmen oft viel schlechter als reine DP-Algorithmen sein können, war seit langem bekannt). • Subtraktion kann reine DP-Algorithmen exponentiell beschleunigen, aber Subtraktion angewandt nur auf die Eingaben ist fast nutzlos (die Beschleunigung kann dann höchstens quadratisch sein). • Sortierung kann reine DP-Algorithmen exponentiell beschleunigen. Während der Arbeit an dem letzten Resultat haben wir auch eine Verbindung mit der klassischen Kirchhoff’schen Formel für effektive Leitwerte in elektrischen Netzwerken entdeckt: über dem tropischen (min,+) Halbkörper ist der effektive Leitwert zwischen zwei Knoten genau die minmax-Distanz zwischen diesen Knoten.
Publications
- Incremental versus non-incremental dynamic programming. Operations Research Letters, 46(3):278–281, 2018
S. Jukna
(See online at https://doi.org/10.1016/j.orl.2018.02.003) - Greedy can beat pure dynamic programming. Inf. Process. Letters, 142:90–95, 2019
S. Jukna and H. Seiwert
(See online at https://doi.org/10.1016/j.ipl.2018.10.018) - Approximation limitations of pure dynamic programming. SIAM J. on Computing, 49(1):170–207, 2020
S. Jukna and H. Seiwert
(See online at https://doi.org/10.1137/18m1196339) - Coin flipping in dynamic programming is almost useless. ACM Trans. on Computation Theory, Article 17, 26 pages, 2020
S. Jukna
(See online at https://doi.org/10.1145/3397476) - Sorting can exponentially speed up pure dynamic programming. Inf. Processing Letters, Article Nr. 105962, 2020
S. Jukna and H. Seiwert
(See online at https://doi.org/10.1016/j.ipl.2020.105962) - Tropical Kirchhoff’s formula and postoptimality in matroid optimization. Discrete Applied Mathematics, 289:12–21, 2021
S. Jukna and H. Seiwert
(See online at https://doi.org/10.1016/j.dam.2020.09.018)
