# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
Additionally, we assume that \(\varepsilon\leq 1\) such that \(\ln{(1+\varepsilon)}=\Theta(\varepsilon)\) and set \(c_{i}^{\min}:=\min_{a\in A}c_{a,i}\), \(c_{i}^{\max}:=\max_{a\in A}c_{a,i}\), and \(C_{i}=\frac{c_{i}^{\max}}{c_{i}^{\min}}\) for \(i\in\{1,\ldots,d\}\). As in the FPTAS presented in [2; 3], ours is exact in one dimension. In our case, we choose the first cost component to be exact meaning that we compute a \((1,1+\varepsilon 1)\)-cover of \(\mathcal{X}\), with \(1\in\mathbb{R}^{d-1}\). The MD-FPTAS assigns a \((d-1)\)-dimensional tensor \(T_{v}\) to each node \(v\in V\). The entries of each tensor in the \((j-1)^{th}\) dimension, \(j\in\{2,\ldots d\}\), are indexed from \(0\) to \(\lfloor\log_{r}(nC_{j})\rfloor\), for an approximation factor \(r=(1+\varepsilon)^{\frac{1}{n-1}}\in\mathbb{R}_{\geq 1}\). At most, one \begin{table}
\begin{tabular}{c c c c} \hline \hline  & **Exact MD-A (Section 3.3)** & **MD-FPTAS (Section 4.2)** & **MD-FPTAS\_T (Section 4.21)** \\ \hline \(d=2\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(1)\) & \(\mathcal{O}(1)\) \\ \(d\geq 3\) & \(\mathcal{O}(L_{v})\subseteq\mathcal{O}(N_{max})\) & \(\mathcal{O}(\mathcal{T})\) & \(\mathcal{O}(1)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Complexity \(\mathcal{C}\) of the dominance checks. \((s,v)\)-path is stored in each entry of \(T_{v}\). With our choice of \(r\), this guarantees the desired polynomial running time and space consumption. The bound on the space consumption can be derived from the size of \(T_{v}\): the length of \(T_{vj}\) becomes \(\left\lfloor\frac{n}{2}\log(nC_{j})\right\rfloor\) for any node \(v\in V\) and \(j\in\{2,\ldots,d\}\) such that, in total, \(T_{v}\) stores at most \(\prod_{i=2}^{d}\left\lceil T_{v,i}\right\rfloor\), a term that is polynomial in the size of the graph and in \(\frac{1}{\epsilon}\). If we allow our FPTAS to only store one (simple) path per entry in the vector, we guarantee the polynomial space consumption of the MD-FPTAS. The position of a \((s,v)\)-path \(p\in\mathcal{X}\) in \(T_{v}\) is computed using the function \(\operatorname{pos}:\mathbb{R}_{\geq 0}^{d}\to\mathbb{N}_{0}^{d-1}\) which is defined componentwise as

\[\operatorname{pos}_{j}(c(p)):= \begin{cases}0&,\text{ if }c_{j}(p)=0\\ 1+\left\lfloor\log_{r}\frac{c_{j}(p)}{\epsilon_{j}^{\min}}\right\rfloor&, \text{ else }\end{cases} ,j\in\{2,\ldots d\}. \tag{5}\]

This justifies the size of the tensors since efficient (simple) paths have at most \((n-1)\) arcs and hence, \(c_{j}(p)\ \leq\ (n-1)\epsilon_{j}^{\max}\). We incorporate the subdivision of the outcome space into Algorithm 1 and, in particular, into the dominance checks made therein. To do so, we consider the blue parts in the pseudocodes from Section 3. In the MD-FPTAS any label \(\ell\) representing a path \(p\) additionally stores \(\operatorname{pos}(c(p))=\operatorname{pos}\left(c_{\ell}\right)\). For ease of exposition, we will write \(\operatorname{pos}(p)\) and \(\operatorname{pos}(\ell)\) from now on. Labels continue to be sorted lexicographically in the priority queue \(Q\) but the dominance checks are done using the labels' pos values: if two distinct labels \(\ell\), \(\ell^{\prime}\) at a node \(v\in V\) fulfill \(\ell_{\ell,1}\leq c_{\ell^{\prime},1}\) and \(\operatorname{pos}_{j}(\ell)\leq\operatorname{pos}_{j}(\ell^{\prime})\) for \(j\in\{2,\ldots d\}\), we say that \(\ell\) pos-dominates \(\ell^{\prime}\) and write \(\ell\preceq_{\operatorname{pos}}\ell^{\prime}\). The new checks are shown in Algorithms 4 and 5. No further modifications w.r.t. Algorithm 1 are needed to obtain the MD-FPTAS from the MD-A. Hence, the MD-FPTAS makes labels permanent after extracting them from the heap. It is guaranteed that at the moment of extraction of a label \(\ell_{v}\) at a node \(v\in V\), there is no label \(\ell_{v}^{\prime}\) in \(L_{v}\) such that \(\ell_{v}^{\prime}\preceq_{\operatorname{pos}}\ell_{v}\) and thus, no two labels with the same pos values will be stored, i.e., nextCandidateLabel and propagate.