Neue Graphen-Algorithmen mittels polyedrischer Methoden

Abstract

In dieser Arbeit werden neue Algorithmen für zwei grundlegende Graphenprobleme vorgestellt. Mit Hilfe von linearen Programmen – darunter auch Programme exponentieller Größe – werden Struktureigenschaften ermittelt die vomAlgorithmus verwendet werden. Etwas überraschend können ähnliche polyedrische Methoden in beiden Graphenproblemen angewendet werden. Der erste Teil der Dissertation widmet sich dem asymmetrischen Handlungsreisendenproblem (Asymmetric Traveling Salesman Problem – ATSP), einem Benchmark-Problem der kombinatorischen Optimierung. Bei diesem Problem geht es darum, die kürzeste Tour für einen erichteten und kantengewichteten Graphen zu finden, die alle Knoten besucht. Seit langem galt es als offen, ob es einen Approximationsalgorithmus für dieses Problem mit einer konstanten Güte gibt. Ein Ergebnis dieser Arbeit ist ein solcher Algorithmus. Der zweite Teil der Dissertation widmet sich dem perfekten Matching-Problem. Zudem wurde in den Achtzigerjahren gezeigt, dass es effiziente parallele Algorithmen für das Matching-Problem gibt, sofern die Verwendung von Zufälligkeit zulässig ist. Allerdings ist es noch offen ob das Matching-Problem in der Komplexitätsklasse NC liegt, also ob Zufälligkeit notwending ist. Diese Arbeit zeigt, dass das Matching-Problem in quasi-NC liegt.