# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
Additionally, for any arc \(a\in A\) let the functions \(c_{a,j}\), \(j\in\{2,\ldots,d\}\) have only non-negative intercepts. Then, the MD-FPTAS computes a \((1+\epsilon)\)-cover of the minimum complete set of efficient paths for \(\mathcal{I}\) computed by the MD-\(A\)._

Proof: The proof is analogous to that of Theorem 4.1 using Equation (9) instead of Equation (8) in the induction step. ### Complexity of the MD-FPTAS

In this section, we set \(C:=\max_{j\in\{2,\ldots,d\}}C_{j}\). Then, each tensor \(T_{v}\) can store at most \(\mathcal{T}:=(\left\lfloor\frac{n}{\epsilon}\log(nC)\right\rfloor)^{d-1}\) paths and when analyzing the MD-FPTAS in terms of \(\mathcal{N}_{\max}\) and \(\mathcal{N}\) as in Section 3, we get

\[c(\tilde{p})\leq r^{k}c(p^{*}).\]0

Recall that the lists \(L_{\varepsilon}\) contain permanent labels that are sorted in lexicographically increasing order. In the biobjective case this implies that they will be sorted increasingly according to the first cost component and simultaneously, decreasingly w.r.t. their pos value (Note that for \(d=2\), \(\operatorname{pos}(\cdot)\) maps to \(\mathbb{R}_{\geq 0}\) so it is well defined to talk about a label's pos value). There are two reasons for this. On one hand we have the monotonicity of the log function and on the other hand, the already discussed fact that for \(d=2\) efficient labels that are sorted lexicographically have an increasing second cost component. Hence, as in the exact case, the complexity \(\mathcal{C}\) of the pos -dominance checks (Algorithms 4 and 5) is constant in the biobjective case and linear (\(\mathcal{O}(\mathcal{T})\)) for \(d\geq 3\). Table 2 shows the time complexity of the different FPTAS for the MOSP problem that we are discussing in this paper. #### 4.2.1. Storing Tensors Explicitly

While the complexity of the MD-FPTAS is lower than that of the Martins-FPTAS, the FPTAS presented in [2] (TZ-FPTAS) is yet to be undercut. This algorithm works similar to the well known Bellman Ford algorithm for the One-to-All Shortest Path Problem and stores the tensor \(T_{v}\) for every node \(v\in V\). In iteration \(i\in\{1,\ldots,n-1\}\), the algorithm computes \((s,v)\)-paths with at most \(i\) edges and does no proper dominance check. Instead, for a newly found path \(p\), the entry \(\text{pos}\left(p\right)\) in \(T_{v}\) is checked: if it is empty, \(p\) is added; if a path already exists, only the one with the lowest costs in the exact dimension (in [2] it is the \(d_{a}\) one) is kept. Since the dominance checks are costly, storing the tensors \(T_{v}\) and checking only the current position yields a great advantage when it comes to the algorithmic complexity. We can adapt the MD-FPTAS such that at every node a tensor \(T_{v}\) is stored. The entries of \(T_{v}\) are 0 or 1 depending on whether a path with the corresponding \(\text{pos}\) value has already been stored in \(L_{v}\). Let \(\ell_{v}\) be a tentative label for a node \(v\) computed in Line 6 of nextCandidateLabel or in Line 2 of propagate. Instead of calling the function BLACK_BOX_DOM, we check if \(T_{v}[\text{pos}\left(\ell_{v}\right)]==0\). In case the tensor entry is indeed set to 0, we add \(\ell_{v}\) to \(L_{v}\) and set \(T_{v}[\text{pos}\left(\ell_{v}\right)]=1\). If the tensor entry is set to 1, we neglect \(\ell_{v}\) since there is a lex. smaller label in \(L_{v}\) with the same \(\text{pos}\)  than \(\ell_{v}\), hence \(\text{pos}\)-dominating \(\ell_{v}\). The suggested adaption increases the space complexity of the MD-FPTAS. Moreover, in general, it will compute more labels than before since checking dominance using \(\preceq_{\text{pos}}\)  is more restrictive than checking pos-equality. However, as in the TZ-FPTAS, the construction of the tensors \(T_{v}\) still guarantees that the number of paths and iterations stays polynomially bounded.