Bibliography | Holzmüller, David: Improved approximation schemes for the restricted shortest path problem. University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis (2016). 27 pages, english.
|
CR-Schema | F.2.2 (Nonnumerical Algorithms and Problems)
|
Abstract | 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.
|
Full text and other links | PDF (716382 Bytes)
|
Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
|
Entry date | September 26, 2018 |
---|