• search hit 1 of 80
Back to Result List

## 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.

### Additional Services

Author: Christoph Hertrich urn:nbn:de:hbz:386-kluedo-54976 41 Sven O. Krumke Bachelor Thesis English 2016/07/29 2016 Technische Universität Kaiserslautern Technische Universität Kaiserslautern 2019/02/07 Fachbereich Mathematik 5 Naturwissenschaften und Mathematik / 510 Mathematik Creative Commons 4.0 - Namensnennung (CC BY 4.0)