Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 4 of 15
Back to Result List

An FPTAS for Dynamic Multiobjective Shortest Path Problems

  • The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.
Metadaten
Author:Pedro Maristany de las CasasORCiD, Ralf BorndörferORCiD, Luitgard KrausORCiD, Antonio Sedeño-NodaORCiD
Document Type:Article
Parent Title (English):Algorithms
Volume:14
Issue:2
First Page:1
Last Page:22
Year of first publication:2021
Preprint:urn:nbn:de:0297-zib-80954
DOI:https://doi.org/https://doi.org/10.3390/a14020043
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.