Algorithms and complexity results for submodular function maximization, traveling salesman and other graph design problems

• Algorithmen und Komplexitätsresultate für Maximierung submodularer Funktionen, das Traveling Salesman und andere Graph Design Probleme

Gottschalk, Corinna; Peis, Britta (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen (2017)
Doktorarbeit

Dissertation, RWTH Aachen University, 2017

Kurzfassung

In der kombinatorischen Optimierung unterscheiden wir zwischen Problemen, die in polynomieller Zeit lösbar sind, und NP-schweren Problemen, für die kein polynomieller Algorithmus existiert außer P= NP. Da es viele Probleme mit unterschiedlichsten Anwendungen gibt, die zu der letztgenannten Kategorie gehören, sind wir trotzdem daran interessiert, gute Lösungen fuer NP-schwere Probleme in polynomieller Zeit zu erhalten. Zu diesem Zweck entwerfen wir Approximationsalgorithmen, die Lösungen berechnen, deren Wert nachweislich nah am Wert einer optimalen Lösung liegt. Wir bezeichnen einen Algorithmus für ein Minimierungsproblem als a-Approximation falls das Verhältnis von Lösungswert und optimalem Wert immer von oben durch a beschränkt werden kann und analog für ein Maximierungsproblem. In dieser Dissertation werden wir vier Probleme behandeln, die im Allgemeinen NP-schwer sind, und sie im Hinblick auf Approximierbarkeit untersuchen. Unsere Ziele sind folglich, Approximationsalgorithmen zu entwerfen und Schranken für die Approximationsgüte zu finden sowie zu verstehen, unter welchen Umständen es polynomielle Algorithmen gibt. Zu Beginn betrachten wir das s-t-Path Traveling Salesman Problem, ein klassisches Netzwerkdesignproblem mit dem Ziel, einen günstigsten Hamiltonpfad in einem vollständigen Graphen zu finden. Wir stellen eine 1.566-Approximation vor, die auf einem neuen Strukturresultat basiert, das zeigt, wie eine LP-Lösung als Konvexkombination bestimmter Spannbäume dargestellt werden kann. Anschließend untersuchen wir das Minimum Fractional Additive Stabilizer Problem. Hier ist unser Ziel, aus einem gegebenen Inputgraphen einen stabilen Graph zu konstruieren indem wir eine minimale Gesamtmenge von Kantengewichten hinzufügen. Wir zeigen, wie dieses Problem auf faktor-kritischen Graphen gelöst werden kann. Dann benutzen wir dies, um einen Approximationsalgorithmus für Graphen, deren Gallai-Edmonds Dekomposition eine bestimmte Struktur hat, zu entwerfen. Außerdem beweisen wir zwei Schranken an die Approximierbarkeit und präsentieren damit auch die erste nicht konstante Schranke für irgendein Graph-Stabilisierungsproblem. Dann betrachten wir eine Verallgemeinerung des Netzwerkdesignproblems, einen minimalen Spannbaum mit k roten Kanten in einem rot-blau gefärbten Graphen zu finden. Es ist seit langem bekannt, dass dieses Problem auf Matroiden effizient gelöst werden kann. Wir verallgemeinern es auf Poset Matroide, bei denen die zugrunde liegende Struktur eine partiell geordnete statt einer ungeordneten Menge ist. Wir untersuchen verschiedene Spezialfälle, von denen einige polynomiell lösbar sind, während bei anderen schwer zu entscheiden ist, ob eine zulässige Lösung existiert. Schließlich analysieren wir die Maximierung submodularer Funktionen auf distributiven Verbänden. Das heißt, die Definitionsmenge ist gegeben durch die Ideale einer partiellen Ordnung statt durch die Teilmengen einer Menge. Wir zeigen Approximationsalgorithmen für verschiedene Varianten, sowohl für unbeschränkte Maximierung als auch für Maximierung mit zusätzlichen Nebenbedingungen, die durch Poset Matroide gegeben sind.