Detailseite
Projekt Druckansicht

Grenzen der dynamischen Programmierung

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2013 bis 2017
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 237501959
 
Erstellungsjahr 2017

Zusammenfassung der Projektergebnisse

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.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung