Algorithms and complexity results for packing and covering problems and robust dynamic network flows under primal-dual aspects

• Algorithmen und Komplexitätsresultate für Packungs- und Überdeckungsprobleme sowie für Robuste Dynamische Netzwerkfluss Probleme unter Primal-Dualen Aspekten

Wierz, Andreas; Peis, Britta (Thesis advisor); Koster, Arie Marinus (Thesis advisor); Skutella, Martin (Thesis advisor)

Aachen (2018)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2018

Abstract

Primal-dual methods have a longstanding history as a tool which proves approximation guarantees for solutions to combinatorial optimization problems. These methods also play a central role in this work. 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. We call a combinatorial optimization problem a weighted covering problem if it can be written in the form \min_{x \in \ZZ_+^n} \left\{ c^T x \mid Ax \geq r \right\}, where $A \in \RR_+^{m \times n}$, $r \in \RR^m$ and $c \in \RR_+^n$. That is, in weighted covering problems, we seek to find integer vectors which are feasible for an inequality system with non-negative coefficients and which minimize a linear objective function. Famous examples include various network design problems, vertex cover, knapsack cover, and optimization over polymatroids. Many covering problems are accompanied by a very simple algorithmic approach which obtains approximate solutions: the primal-dual greedy algorithm. Our main result is the characterization of a subclass of weighted covering problems for which the primal-dual greedy algorithm is proven to (1) always obtain a feasible solution which (2) has a bounded approximation guarantee. Our framework describes the approximation guarantee in terms of characteristics of the inequality system $(A,r)$ and independent of the cost function $c$. For many problems, including the list of examples above, 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. Our characterization is smallest possible in the sense that the removal of any one of the required properties results in a situation in which the analyzed primal-dual greedy algorithm no longer necessarily computes feasible solutions. In the second part of this thesis, we discuss static and dynamic maximum flow problems under uncertainty. In the static maximum flow problem, the goal is to maximize the total throughput in a capacitated network. The dynamic variant considers an additional temporal component and the goal is to maximize the throughput within a given time horizon while flow takes time in order to traverse the network. In our results, we consider these problems subject to uncertain input data. That is, we seek to find solutions which are robust against edge failures and edge delays, respectively, in the static and dynamic case. In either case, solutions are evaluated under a robust worst-case perspective. 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.