8415
2021
eng
bachelorthesis
0
--
--
--
A Label Setting Multiobjective Shortest Path FPTAS
Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.
publish
Ralf BorndÃ¶rfer
Luitgard Kraus
Niels Lindner
Niels Lindner
Pedro Maristany de las Casas
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
MODAL-Gesamt
Kraus, Luitgard
Network Optimization
MODAL-MobilityLab
Freie UniversitÃ¤t Berlin