Algorithms and complexity results for packing and covering problems and robust dynamic network flows under primal-dual aspects

• Algorithmen und Komplexitätsresultate für Packungs- und Überdeckungsprobleme sowie für Robuste Dynamische Netzwerkfluss Probleme unter Primal-Dualen Aspekten

Wierz, Andreas; Peis, Britta (Thesis advisor); Koster, Arie Marinus (Thesis advisor); Skutella, Martin (Thesis advisor)

Aachen (2018)
Doktorarbeit

Dissertation, RWTH Aachen University, 2018

Kurzfassung

Primal-Duale Methoden blicken auf eine erfolgreiche Vergangenheit im Bezug auf ihre Nutzbarkeit als Werkzeug zur Beweisführung von Approximationsresultaten in der Kombinatorischen Optimierung zurück. In dieser Arbeit spielen solche Methoden auch eine zentrale Rolle. Wir betrachten eine allgemeine Klasse von gewichteten Überdeckungsproblemen, sowie statische und dynamische Netzwerkfluss Probleme unter Unsicherheiten. Für beide Probleme liefern wir theoretische Einsichten und entwickeln Approximationsalgorithmen. Im Bezug auf gewichtete Überdeckungsprobleme beschäftigen wir uns mit der Charakterisierung einer Subklasse von Instanzen, für welche der klassische Primal-Duale Greedy Algorithmus eine geeignete Lösungsstrategie darstellt. Für Netzwerkfluss Probleme evaluieren wir die Nutzbarkeit von klassischen Lösungskonzepten unter der Annahme, dass Eingabedaten mit Unsicherheit behaftet sind. Im statischen Fall beschreiben diese Unsicherheiten den Ausfall von Kanten, im dynamischen Fall die Verzögerung von Fahrzeiten auf Kanten. Unser Hauptresultat bezüglich gewichteten Überdeckungsproblemen ist die Charakterisierung einer Subklasse von Instanzen, für die der klassische Primal-Duale Greedy Algorithmus beweisbar (1) immer eine zulässige Lösung findet, welche (2) eine beschränkte Gütegarantie einhält. Unser Framework beschreibt die Gütegarantie auf Basis von Charakteristiken von Ungleichungssystemen $(A,r)$, unabhängig von der Kostenfunktion. Für eine Vielzahl von Problemen stimmen die Gütegarantien, welche mit unserem Framework erreicht werden, mit den bis jetzt besten bekannten Gütegarantien überein. Weiter liefern wir die ersten bekannten Gütegarantien für das Precedence Constrained Knapsack Cover Problem sowie für das Flow Cover on multiple Lines Problem. Abschließend zeigen wir, dass unsere Charakterisierung kleinstmöglich ist, im Sinne, dass die Entfernung jeder einzelnen unserer Charakterisierungsbedingungen dazu führt, dass der Primal-Duale Greedy Algorithmus nicht länger notwendigerweise zulässige Lösungen berechnet. Im zweiten Teil dieser Arbeit beschäftigen wir uns mit statischen und dynamischen Netzwerkfluss Problemen unter Unsicherheiten. Im statischen Fall betrachten wir die Unsicherheit von Kantenausfällen, im dynamischen Fall diejenige, dass Fahrzeiten auf Kanten verspätet sein können. Beide Varianten betrachten wir aus einer robusten Worst-Case Perspektive. Für das statische Maximale Fluss Problem unter Unsicherheiten ist unser größter Beitrag die Einführung und Analyse eines Hybridmodells. Das Modell enthält das $\Gamma$-robuste Maximale Fluss Problem sowie ein stochastisches Maximales Fluss Problem an seinen Extremen. Bezüglich des Hybridmodells betrachten wir die Qualität von Lösungen die entsteht, wenn das Hybridmodell keinen Zugriff auf eine vollständige Wahrscheinlichkeitsverteilung über die Szenarien verfügt, sondern stattdessen eine kleine Stichprobe nutzt. Für das dynamische Netzwerkfluss Problem führen wir ein $\Gamma$-robustes Modell ein und diskutieren Verallgemeinerungen von klassischen Lösungskonzepten. Unser Hauptbeitrag beschäftigt sich mit der Analyse der Lösungsqualität von zeitlich wiederholten Flüssen unter Einbeziehung von Unsicherheiten. Es ist bekannt, dass die Klasse von zeitlich wiederholten Flüssen im nominalen Fall optimal ist. Unter Unsicherheiten zeigen wir, dass dies nicht länger der Fall ist, indem wir obere und untere Schranken an die Lösungsqualität von zeitlich wiederholten Flüssen liefern.

Einrichtungen

• Fachgruppe Mathematik [110000]
• Lehr- und Forschungsgebiet Diskrete Optimierung [113320]
• Lehrstuhl für Management Science [815110]