Complexity of bulk-robust combinatorial optimization problems

Abstract

This thesis studies three robust combinatorial optimization problems on graphs. Most robust combinatorial optimization problems assume that the cost of the resources, e.g. edges in a graph, are uncertain. In this thesis, however, we study the so called bulk-robust approach which models the uncertainty in the underlying combinatorial structure. To be more precise, in the bulk-robust model we are given an explicit list of scenarios comprising a set of resources each, which fail if the corresponding scenario materializes. Additionally, we are given a property that we have to obtain such as 'containing a perfect matching', 's-t-connectivity', or 'being connected', which may arise from a fundamental combinatorial optimization problem. The goal of the bulk-robust optimization problem is to find a minimum weight set of resources such that the desired property is satisfied no matter which scenario materializes, i.e. no matter which set of resources from the list is removed. We study the bulk-robust bipartite matching problem, the bulk-robust k-edge disjoint s-t-paths problem, and the bulk-robust minimum spanning tree problem. We investigate the complexity of the three problems and show that most of them are hard to approximate even if the list of scenarios consists of singletons only. We complement these inapproximability results with polynomial-time approximation algorithms that essentially match the hardness results. Furthermore, we present FPT and XP algorithms and consider special graph classes that allow for a polynomial-time exact algorithm.

In dieser Arbeit werden drei robuste kombinatorische Optimierungsprobleme auf Graphen behandelt. Die meisten robusten kombinatorischen Optimierungsprobleme nehmen an, dass die Kosten der Ressourcen, z.B. Kanten in einem Graph, unsicher sind. Diese Arbeit jedoch behandelt den Ansatz der sogenannten bulk-Robustheit, die Unsicherheiten in der kombinatorischen Struktur widerspiegelt. Genauer gesagt ist im bulk-robusten Modell eine explizite Liste von Szenarien gegegeben und jedes dieser Szenarien enthält eine Menge von Ressourcen, die ausfällt, wenn das entsprechende Szenario eintritt. Zusätzlich ist noch eine Eigenschaft gegeben, die wir erzeugen müssen. Diese Eigenschaft könnte beispielsweise sein, dass der resultierende Graph ein perfektes Matching enthält, zwei bestimmte Knoten miteinander verbindet oder zusammenhängend ist. Das Ziel des bulk-robusten Optimierungsproblems ist es, eine kosten-minimale Menge von Ressourcen zu finden, sodass die gewünschte Eigenschaft erfüllt ist, egal welches Szenario eintrifft, d.h. unabhängig davon, welche Menge von Resourcen der Liste von der Lösung entfernt wird. Diese Arbeit behandelt das bulk-robuste bipartite Matchingproblem, das bulk-robuste k-Kanten disjunkte s-t-Wege Problem und das bulk-robuste minimale Spannbaum Problem. Wir beschäftigen uns mit der Komplexität der drei Probleme und zeigen, dass die meisten sogar dann schwer zu approximieren sind, wenn die Liste der Szenarien nur aus einelementigen Mengen besteht. Wir komplementieren diese nicht-Approximierbarkeitsresultate mit effizienten Approximationsalgorithmen, deren Güte im Wesentlichen den hardness-Resultaten entspricht. Darüber hinaus präsentieren wir FPT und XP Algorithmen und entwickeln effiziente exakte Algorithmen für spezielle Graphklassen.