On Flows, Paths, Roots, and Zeros

Abstract

This thesis has two parts; in the first of which we give new results for various network flow problems. (1) We present a novel dual ascent algorithm for min-cost flow and show that an implementation of it is very efficient on certain instance classes. (2) We approach the problem of numerical stability of interior point network flow algorithms by giving a path following method that works with integer arithmetic solely and is thus guaranteed to be free of any nu-merical instabilities. (3) We present a gradient descent approach for the undirected transship-ment problem and its special case, the single source shortest path problem (SSSP). For distrib-uted computation models this yields the first SSSP-algorithm with near-optimal number of communication rounds. The second part deals with fundamental topics from algebraic computation. (1) We give an algorithm for computing the complex roots of a complex polynomial. While achieving a com-parable bit complexity as previous best results, our algorithm is simple and promising to be of practical impact. It uses a test for counting the roots of a polynomial in a region that is based on Pellet's theorem. (2) We extend this test to polynomial systems, i.e., we develop an algorithm that can certify the existence of a k-fold zero of a zero-dimensional polynomial system within a given region. For bivariate systems, we show experimentally that this approach yields signifi-cant improvements when used as inclusion predicate in an elimination method.

Im ersten Teil dieser Dissertation präsentieren wir neue Resultate für verschiedene Netzwerkflussprobleme. (1)Wir geben eine neue Duale-Aufstiegsmethode für das Min-Cost-Flow- Problem an und zeigen, dass eine Implementierung dieser Methode sehr effizient auf gewissen Instanzklassen ist. (2)Wir behandeln numerische Stabilität von Innere-Punkte-Methoden fürNetwerkflüsse, indem wir eine solche Methode angeben die mit ganzzahliger Arithmetik arbeitet und daher garantiert frei von numerischen Instabilitäten ist. (3) Wir präsentieren ein Gradienten-Abstiegsverfahren für das ungerichtete Transshipment-Problem, und seinen Spezialfall, das Single-Source-Shortest-Problem (SSSP), die für SSSP in verteilten Rechenmodellen die erste mit nahe-optimaler Anzahl von Kommunikationsrunden ist. Der zweite Teil handelt von fundamentalen Problemen der Computeralgebra. (1) Wir geben einen Algorithmus zum Berechnen der komplexen Nullstellen eines komplexen Polynoms an, der eine vergleichbare Bitkomplexität zu vorherigen besten Resultaten hat, aber vergleichsweise einfach und daher vielversprechend für die Praxis ist. (2)Wir erweitern den darin verwendeten Pellet-Test zum Zählen der Nullstellen eines Polynoms auf Polynomsysteme, sodass wir die Existenz einer k-fachen Nullstelle eines Systems in einer gegebenen Region zertifizieren können. Für bivariate Systeme zeigen wir experimentell, dass eine Integration dieses Ansatzes in eine Eliminationsmethode zu einer signifikanten Verbesserung führt.