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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Verfasserangaben:Christoph Hertrich
URN (Permalink):urn:nbn:de:hbz:386-kluedo-54976
Betreuer:Sven O. Krumke
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):29.07.2016
Jahr der Veröffentlichung:2016
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):07.02.2019
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
Lizenz (Deutsch):Creative Commons 4.0 - Namensnennung (CC BY 4.0)