|Holzmüller, David: Improved approximation schemes for the restricted shortest path problem. |
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit (2016).
27 Seiten, englisch.
|CR-Klassif.||F.2.2 (Nonnumerical Algorithms and Problems)|
In this thesis we present several variants of an approximation scheme for the restricted shortest path problem. This problem concerns finding a shortest path with respect to one criterion while not exceeding a length bound with respect to another criterion. After formally introducing the problem, we describe the approximation scheme by Lorenz and Raz. Our algorithm then introduces additional steps to reduce the runtime complexity from O(|E|n(1/epsilon + log log n)) to O(|E|n(1/epsilon + \log \log \log n)). A variant of this algorithm yields a complexity of O(|E|n(1/epsilon + (n log n) / m)), which is a further improvement for sufficiently dense graphs. Furthermore, a slight modification leads to an O(|E|n(1/epsilon + 1))-algorithm for directed acyclic graphs, providing an arguably easier algorithm than the algorithm proposed by Ergun et al.
|PDF (716382 Bytes)|
|Abteilung(en)||Universität Stuttgart, Institut für Formale Methoden der Informatik, Algorithmik|
|Eingabedatum||26. September 2018|