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

Author: | Christoph Hertrich |
---|---|

URN (permanent link): | urn:nbn:de:hbz:386-kluedo-54976 |

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: | Fachbereich Mathematik |

DDC-Cassification: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |

Licence (German): | Creative Commons 4.0 - Namensnennung (CC BY 4.0) |