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 Entscheidungsprobleme. Dieses algorithmische Prinzip ist so natürlich, dass man kaum hinterfragt, ob es auch optimal ist. Genau diese Frage haben wir gestellt und in vielen Fällen beantworten können. Viele fundamentale DP-Algorithmen sind „rein”, da ihre Rekursionsgleichungen nur Min bzw. Max und die Addition als Operationen benutzen. Ein natürliches mathematisches Model für solche Algorithmen sind die sogenannten tropischen (min, +) bzw. (max, +) Schaltkreise. Hier handelt es sich um konventionelle Schaltkreise, deren Gatter die Operationen Min bzw. Max sowie die Addition ausführen. Die Anzahl der Gatter entspricht der Anzahl der Operationen, die der entsprechende reine DP-Algorithmus anwenden muss. Untere Schranken für die Größe tropischer Schaltkreise zeigen also die Grenzen der reinen DP-Algorithmen. Der Nachweis solcher Schranken war das Hauptziel des Projektes. In einem 0-1 Optimierungsproblem haben wir Elemente einer Grundmenge (z.B. Knoten oder Kanten) sowie eine Familie legaler Lösungen (Teilmengen der Grundelementen). Das Ziel ist, für jede Zuweisung nicht-negativer Gewichten zu Elementen der Grundmenge, das minimale oder maximale Gewicht einer legalen Lösung zu bestimmen. Es war seit langem bekannt, dass die tropische Komplexität homogener Optimierungsproblemen (wenn alle legale Lösungen die gleiche Anzahl von Elementen der Grundmenge besitzen) durch die monotone arithmetische Komplexität der entsprechenden Polynome nach unten beschränkt ist. Da wir mächtige untere Schranken Methoden für die letztere Komplexität zur Verfügung haben, ist somit auch die tropische Komplexität homogener Optimierungsproblemen bereits relativ gut verstanden. In dem Fall nicht-homogener Problemen sieht jedoch die Situation viel düsterer aus, da die Lücke zwischen tropischer und arithmetischer Komplexität sogar exponentiell groß sein kann. Ein prominentes Beispiel dafür ist die Bestimmung des kürzesten s-t Weges. Es ist einerseits bekannt, dass die arithmetische Komplexität dieses Problem exponentiell ist, während der Bellman–Ford DP-Algorithmus das Problem in kubischer Zeit löst. Daher haben wir uns in dem Projekt auf die tropische Kompexität nicht-homogener Optimierungsproblemen konzentriert und eine Reihe unterer Schranken bewiesen, wie zum Beispiel: • Die Optimalität des Bellman–Ford Algorithmus unter allen sukzessiven DP-Algorithmen; • allgemeine untere Schranken für die DP-Komplexität nicht-homogener Probleme; • allgemeine untere Schranken für die Komplexität abzählender DP-Algorithmen. (Ein reiner DP-Algorithmus ist sukzessiv, wenn in jeder Addition eine der Eingaben eine Variable ist. So ist z.B. der Bellman–Ford Algorithmus sukzessiv.) Es ist uns aber nicht gelungen, die Optimalität des Bellman–Ford Algorithmus in der breiteren Klasse reiner (aber nicht-sukzessiver) DP-Algorithmen zu zeigen. Es gibt (wenn auch nur künstlich konstruierte) Optimierungsprobleme, die man nicht mit sukzessiven DP-Algorithmen in polynomieller Zeit lösen kann, die aber leicht mit nicht-sukzessiven DP-Algorithmen gelöst werden können. Es bleibt somit nicht ausgeschlossen, dass auch der Bellman–Ford Algorithmus durch nicht-sukzessive DP-Algorithmen beschleunigt werden kann.
Publications
- (2017) Minkowski Complexity of Sets: An Easy Lower Bound. The American Mathematical Monthly 124 (8) 749
Jukna, Stasys
(See online at https://doi.org/10.4169/amer.math.monthly.124.8.749) - Lower bounds for monotone counting circuits. Discrete Appl. Math., 2016
S. Jukna
(See online at https://dx.doi.org/10.1016/j.dam.2016.04.024) - Advances in Network Complexity, Quantitative and Network Biology, chapter Computational complexity of graphs, pages 99–154. Willey-Blackwell, 2013. ISBN 978-3-527-33291-5
S. Jukna
- Complexity of linear boolean operators. Foundations and Trends in Theoretical Comput. Sci., 9(1):1–123, 2013
S. Jukna and I. Sergeev
(See online at https://dx.doi.org/10.1561/0400000063) - Lower bounds for tropical circuits and dynamic programs. Theory of Comput. Syst., 57(1):160– 194, 2015
S. Jukna
(See online at https://doi.org/10.1007/s00224-014-9574-4) - On the optimality of Bellman-Ford-Moore shortest path algorithm. Theoret. Comput. Sci., 628:101–109, 2016
S. Jukna and G. Schnitger
(See online at https://doi.org/10.1016/j.tcs.2016.03.014) - Tropical complexity, Sidon sets and dynamic programming. SIAM J. Discrete Math., 30(4):2064– 2085, 2016
S. Jukna
(See online at https://doi.org/10.1137/16M1064738)
