# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 1 Introduction
### Literature Review  
Multiobjective optimization problems and, in particular, MOSP problems, have been extensively investigated in the literature. Very good general introductions are provided by, e.g., [PERSON] and [PERSON] [5], [PERSON] [6], or [PERSON] and [PERSON] [7]. The theoretical foundation and the algorithmic development of MOSP problems are reviewed in [PERSON] and [PERSON] [8], [PERSON] and [PERSON] [9], [PERSON] [10], [PERSON] [11], or [PERSON] and [PERSON] [12].  
In the 1970s, [PERSON] [13] considered the MOSP problem for the first time, studying two objective functions. This Biobjective Shortest Path problem was also considered by [PERSON] [1], who came up with the first label-setting algorithm. [PERSON] [14] showed that the MOSP problem is \(NP\)-complete and [PERSON] [15] generalized [PERSON]'s algorithm for the general multiobjective case. Since then, [PERSON]'s algorithm has served as the benchmark for solving MOSP problems. Recently, [PERSON] and [PERSON] [16] and [PERSON] et. al. [17] devised the Biobjective and Multiobjective Dijkstra algorithms (B/MD-A): new label setting algorithms for MOSP problems that have not only superior computational complexity, but are also efficient in practice.  
Turning to approximation, [PERSON] and [PERSON] [18] set a milestone in the field of approximation algorithms for multiobjective optimization problems. They proved that for a multiobjective optimization problem with \(d\) objectives and an \(\varepsilon>0\), a \((1+\varepsilon)\) Pareto curve of size \(O(\frac{4B}{\varepsilon})^{d-1}\) exists. Here, \(B\) is the number of bits required to represent the values that the objective functions can take (\(B\) is assumed to be polynomially bounded). They also constructed the first general FPTAS for MOSP problems. It was superseded by the method of [PERSON] and [PERSON] [2], who presented an FPTAS for the MOSP problem inspired by the classical Bellman Ford algorithm for Shortest Path problems. Their main idea is to subdivide the space of possible path costs into polynomially (in the size of the input and \(1/\varepsilon\)) many cells and admit just one path per cell. The right choice of the subdivision guarantees that if a path is rejected because its cell is occupied, the quality loss remains bounded. This produces a \((1+\varepsilon)\)-cover of the exact set of efficient paths. The idea was picked up by [PERSON] et al. [3] who managed to pair [PERSON]'s algorithm with the subdivision of the outcome space introduced in [2]. The result was an FPTAS for MOSP problems that is worse regarding the theoretical running time, but performs better in computation. Based on this work, [PERSON] and [PERSON] [4] recently published an extensive comparison of different label ordering and selecting strategies.  
The literature considering MOSP instances with dynamic, also called time-dependent, cost functions is scarce. [PERSON] and [PERSON] [19] presented an algorithm for non-monotone increasing arc cost functions that does not reduce to Dynamic Programming. [PERSON] et al [20] mention the necessity to tackle this kind of problems on train networks and use [PERSON]'s algorithm to solve them without going into details. Our label setting algorithm for Dyn-MOSP problems considers only arc cost functions that fulfill the FIFOproperty. An extensive analysis of the implications of this condition on the solvability of single-objective Time-Dependent Shortest Path problems is given by [PERSON] et al. (2018).