Title:	Approximation Algorithms for Multistage Subgraph Problems
Authors:	Troost, Niklas Johannes
ORCID of the author:	https://orcid.org/0000-0001-7412-2770
Thesis advisor:	Prof. Dr. Markus Chimani
Thesis referee:	Prof. Dr. Christian Komusiewicz
Abstract:	The concepts of classical graph theory offer a framework for modeling problems from almost all areas of life. Temporal graphs in particular provide a way to represent and analyze dynamic data, enabling algorithmic solutions to problems dealing with structures that change over time. For the extension to time-related data, different modifications of the graph concept can be useful, depending on the optimization goal. In this work, the focus is on the analysis of problems on finite sequences of graphs whose sequence members are to be read as snapshots of the same graph at different points in time. The key topic is to solve a given combinatorial optimization problem on a sequence of graphs such that the resulting solution sequence satisfies two conditions: (i) each solution is optimal for its respective graph and (ii) solutions of successive graphs are as similar as possible. Problems of this abstract form are called multistage problems, since their instances consist of multiple stages. First, the classical assignment problem Maximum Matching is exemplarily transferred into such a multistage setting. For the two resulting problems MIM and MUM, various approximation algorithms and reductions are developed. The algorithmic approaches for MIM can be generalized to apply to a broad class of multistage formulations of classical problems in graph theory. This general class of problems on multistage graphs, the so-called Multistage Subgraph Problems, is the focus of the second part of this thesis. After discussing the corresponding definitions and adapted algorithms, we present numerous examples of MSPs, where these adapted algorithms can be applied. As we also study the complexity of each example, this provides an overview of the similarities and differences of such multistage problems. In a third part, the performance of the approximation algorithms in practice is investigated by applying them to example instances for the Multistage Shortest Path problem. A comparison is made with derived heuristics and an exact (but slow) algorithm, investigating their respective solution quality and running time. Additional problem-specific results on Multistage Shortest Path and Multistage Minimum Weight Spanning Tree complete the thesis.
URL:	https://doi.org/10.48693/450 https://osnadocs.ub.uni-osnabrueck.de/handle/ds-2024011710256
Subject Keywords:	Multistage Graphs; Complexity Theory; Approximation Algorithms
Issue Date:	17-Jan-2024
License name:	Attribution 3.0 Germany
License url:	http://creativecommons.org/licenses/by/3.0/de/
Type of publication:	Dissertation oder Habilitation [doctoralThesis]
Appears in Collections:	FB06 - E-Dissertationen

This item is licensed under a Creative Commons License