# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
Figure 5 gives a visual impression of the running times: on the left hand side we compare the BDA with the FPTAS-BDA and notice how the solution time of the exact algorithm grows exponentially with the number of computed paths. The FPTAS is not faster than the exact algorithms when the number of labels is similar, but on the bigger EXP graphs it saves a lot of labels. On the right hand side we compare the Martins-FPTAS and the BDA-FPTAS. We can see that the running time growth of the BDA is much slower. Figure 5: BDA exact (green), BD-FPTAS (yellow) and Martins-FPTAS (blue) on exponential instances. \(\varepsilon=0.05\). \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & & & \multicolumn{4}{c}{**Martins**} & \multicolumn{4}{c}{**BDA**} \\ \hline  & & \(\mathcal{N}\) & **Exact \(t[s]\)** & \multicolumn{4}{c}{**FPTAS \(t[s]\)**} & \multicolumn{4}{c}{**Exact \(t[s]\)**} & \multicolumn{4}{c}{**FPTAS \(t[s]\)**} \\ \hline  & & & & 0.05 & 0.5 & 1 & & 0.05 & 0.5 & 1 \\ \cline{3-10} EXP & avg & 338,611 & 524.5146 & 0.3062 & 0.0077 & 0.0046 & 0.1545 & 0.0109 & 0.0032 & 0.0025 \\  & min & 4 & 0.0001 & 0.0001 & 0.0001 & 0.0001 & 0.0001 & 0.0001 & 0.0001 & 0.0001 \\  & max & 1,572,862 & 4213.4131 & 8.1309 & 0.1652 & 0.0658 & 36.6369 & 0.0811 & 0.0229 & 0.0176 \\ \hline GRID & avg & 872,717 & 0.9005 & 1.0308 & 1.0323 & 1.0030 & 0.6181 & 0.9846 & 0.9891 & 0.9534 \\  & min & 8189 & 0.0009 & 0.0024 & 0.0011 & 0.0038 & 0.0015 & 0.0013 & 0.0038 & 0.0034 \\  & max & 5,381,078 & 6.8469 & 7.7819 & 7.8717 & 7.8638 & 4.2258 & 6.8425 & 6.8795 & 6.7666 \\ \hline NET & avg & 597,998 & 2.3356 & 2.7183 & 2.7106 & 2.6828 & 0.7214 & 1



The biobjective GRID and NET instances unveil the major drawback of the used approximation techniques: on graphs with a realistic/practical amount of nodes, the value of \(r=(1+\varepsilon)^{\frac{1}{n-1}}\) is very close to 1 and the pos values of any two different paths are almost always distinct. Hence, the exact algorithms are faster than the FPTAS since the computation time of pos is non negligible in practice and no labels are saved. In [3] the authors overcome this problem by choosing huge values for \(\varepsilon\). Then, they compute an a posteriori approximation that always turns out to be much better than \(\varepsilon\) but there is no guarantee for it. Instead, we focus on values for \(\varepsilon\) that are consistent with the assumption \(\varepsilon\leq 1\) that we made in Section 4. The consequence is indeed that the average FPTAS speedup for \(\varepsilon=0.05\) on GRID is \(\times 1.66\) and on NET instances it is \(\times 3.23\), i.e., in both cases a slowdown. On both instance sets the FPTAS solutions contained almost all exact solutions and even increasing \(\varepsilon\) up to 1 did not have a noteworthy impact. All algorithms were able to solve all instances in these two sets within the time limit. Figure 6 compares both FPTAS and consolidate the impression gained from the EXP instances: the running time advantage of the MD-FPTAS gets bigger as the number of efficient paths grows. #### 5.2.2 Static Three Objective Results

Instances with three objectives are much harder to solve. In Table 4, we summarize the results obtained from the One-to-One queries ran on GRID3D instances and from the One-to-All queries ran on NET3D instances. We observe the same behavior as in the \(2D\) instances: a solid running time advantage for the MD-FPTAS on average (\(\times 1.70\) on GRID3D instances and \(\times 1.46\) on NET3D instances) for \(\varepsilon=0.05\) but slower running times than in the exact counterparts. In these experiments all algorithms always computed always the same amount of labels per instance. Figure 7 shows the comparison of both FPTAS' running times depending on the number of computed paths. In both instance sets the Martins-FPTAS failed to solve bigger instances within the time limit. The overall trend mirrors the biobjective results as the running time of the MD-FPTAS grows considerably slower than that of the Martins-FPTAS.