ISBN 9783843935340

978-3-8439-3534-0, Reihe Mathematik

Andreas Wierz
Algorithms and Complexity Results for Packing and Covering Problems and Robust Dynamic Network Flows under Primal-Dual Aspects

176 Seiten, Dissertation Rheinisch-Westfälische Technische Hochschule Aachen (2018), Softcover, A5

Zusammenfassung / Abstract

Primal-dual methods have a longstanding history as a tool which proves approximation guarantees for solutions to combinatorial optimization problems. In this thesis, we investigate a general class of weighted covering problems, and static and dynamic network flow problems under uncertainty. We provide new theoretic insights and design approximation algorithms for both problems. For weighted covering problems, we focus on the characterization of a subclass of instances for which the primal-dual greedy algorithm is a viable solution strategy. For network flow problems, we evaluate classical solution concepts under uncertainty, that is, when edges fail in the static case and when edges are subject to delays in the dynamic setting.

For weighted covering problems, our main result is the characterization of a subclass of weighted covering problems for which the primal-dual greedy algorithm is proven to always obtain a feasible solution which has a bounded approximation guarantee. Our framework describes the approximation guarantee in terms of characteristics of an inequality system (A,r) and independent of the cost function. For many problems, the bounds from our framework match the best known results from the literature. It also covers new results, proving approximation guarantees for the precedence constrained knapsack cover problem and for a natural generalization of the flow cover on a line problem.

For the static maximum flow problem subject to uncertainty, our main contribution is the introduction of a hybrid model and its analysis. The model contains the Gamma-robust maximum flow problem and a stochastic variant as its extremes. For this hybrid model, we analyze the quality of solutions when a full characterization of the probability distribution of the stochastic model is unknown and only a small sample is available.

In the dynamic variant, we first introduce a Gamma-robust model and discuss generalizations of classical solution concepts. Our main contribution is the analysis of the solution quality of temporally repeated solutions under uncertainty. It is well-known that the class of temporally repeated solutions is optimum if all input data is certain. Under uncertainty, we show that this is no longer the case by providing lower and upper bounds on the optimality gap of temporally repeated solutions when compared to general solutions.