Thema dieser Masterarbeit ist robuste Optimierung im Rahmen von Unsicherheit, insbesondere robuste und umleitbare Flüsse in Netzwerken mit ausfallenden Kanten. Im bekannten Problem Maximum Robust Flow [DM17] wird ein Fluss durch einen gerichteten Graphen geschickt und dann durch die Zerstörung einer bekannten Anzahl von Kanten unterbrochen. Der gesamte Fluss auf Pfaden, die durch zerstörte Kanten führen, geht verloren. Ziel ist es, den übrig gebliebenen Fluss nach Ausfall der Kanten zu maximieren. Wir präsentieren eine Variation dieses Problems namens Maximum Scaled Robust Flow, bei dem die Höhe an zerstörtem Fluss mit einem linearen Faktor skaliert wird. Das Problem ist polynomiell lösbar, wenn nur eine einzige Kante ausfällt, und NP-schwer, wenn die Zahl an ausfallenden Kanten unbekannt ist. Für kleine Beträge des Skalierungsfaktors sind alle Lösungen des Problems maximale Netzwerk-Flüsse. Wenn der Skalierungsfaktor größer ist als eine Zahl abhängig von der Konnektivität des zu Grunde liegenden Graphen, dann ist der Null-Fluss die einzige optimale Lösung. Durch Beispiele wird gezeigt, dass die bewiesenen Schranken scharf sind. Eine Variation mit affiner Skalierung ist polynomiell lösbar, wenn nur eine Kante zerstört wird. Das Gleiche gilt für eine Version, die auf kantenbasierten Flüssen für eine feste Anzahl von zerstörten Kanten definiert ist.
Beim Maximum Reroutable Flow-Problem [MMO17] muss der gesamte Fluss, der an den Ausfall einer einzigen Kante verloren geht, lokal im Graphen mit Hilfe der verfügbaren Kapazitäten umgeleitet werden. Der Zielfunktionswert des Problems ist durch den Wert des ursprünglichen Flusses gegeben. Die strikte Version des Problems, Maximum Strictly Reroutable Flow, gibt strengere Bedingungen an die für das Umleiten verfügbaren Kapazitäten vor. Wir führen die Variationen Maximum Optional Reroutable Flow und Maximum Strictly Optional Reroutable Flow ein, bei denen Umleiten nach dem Ausfall der Kante möglich, aber nicht zwingend notwendig ist. Der Zielfunktionswert wird durch die Kante bestimmt, die nach Ausfall und optionalem Umleiten den schlechtesten Flusswert liefert. Wir beweisen, dass das strikte Problem in polynomieller Zeit lösbar ist und dass eine 2-Approximation für das nicht-strikte Problem existiert. Das Umleiten optional zu machen, verbessert im Vergleich zum ursprünglichen Problem, Maximum Reroutable Flow, den Zielfunktionswert. Wir beweisen, dass Maximum Robust Flow immer einen kleineren Zielfunktionswert als Maximum Optional Reroutable Flow hat und dass es eine polynomielle Reduktion von ersterem zu letzterem gibt. Schließlich lösen wir Maximum Optional Reroutable Flow und dessen strikte Version auf Einheitskapazitäts-Netzwerken, indem wir einen expliziten Zielfunktionswert angeben.
«
Thema dieser Masterarbeit ist robuste Optimierung im Rahmen von Unsicherheit, insbesondere robuste und umleitbare Flüsse in Netzwerken mit ausfallenden Kanten. Im bekannten Problem Maximum Robust Flow [DM17] wird ein Fluss durch einen gerichteten Graphen geschickt und dann durch die Zerstörung einer bekannten Anzahl von Kanten unterbrochen. Der gesamte Fluss auf Pfaden, die durch zerstörte Kanten führen, geht verloren. Ziel ist es, den übrig gebliebenen Fluss nach Ausfall der Kanten zu maximiere...
»