Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
• Treffer 11 von 50
Zurück zur Trefferliste

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