A Parametric View on Robust Graph Problems

  • For some optimization problems on a graph \(G=(V,E)\), one can give a general formulation: Let \(c\colon E \to \mathbb{R}_{\geq 0}\) be a cost function on the edges and \(X \subseteq 2^E\) be a set of (so-called feasible) subsets of \(E\), one aims to minimize \(\sum_{e\in S} c(e)\) among all feasible \(S\in X\). This formulation covers, for instance, the shortest path problem by choosing \(X\) as the set of all paths between two vertices, or the minimum spanning tree problem by choosing \(X\) to be the set of all spanning trees. This bachelor thesis deals with a parametric version of this formulation, where the edge costs \(c_\lambda\colon E \to \mathbb{R}_{\geq 0}\) depend on a parameter \(\lambda\in\mathbb{R}_{\geq 0}\) in a concave and piecewise linear manner. The goal is to investigate the worst case minimum size of a so-called representation system \(R\subseteq X\), which contains for each scenario \(\lambda\in\mathbb{R}_{\geq 0}\) an optimal solution \(S(\lambda)\in R\). It turns out that only a pseudo-polynomial size can be ensured in general, but smaller systems have to exist in special cases. Moreover, methods are presented to find such small systems algorithmically. Finally, the notion of a representation system is relaxed in order to get smaller (i.e. polynomial) systems ensuring a certain approximation ratio.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Author:Christoph Hertrich
Place of publication:41
Advisor:Sven O. Krumke
Document Type:Bachelor Thesis
Language of publication:English
Publication Date:2016/07/29
Year of Publication:2016
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Date of the Publication (Server):2019/02/07
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Creative Commons 4.0 - Namensnennung (CC BY 4.0)