# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
As a consequence, the running time of this variant of the MD-FPTAS for \(d\geq 3\) objectives becomes

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

As shown in Table 2, this is the best known running time bound for an FPTAS for MOSP problems. ## 5 Computational Results

In this section we provide evince the computational efficiency of the MD-FPTAS in comparison to Martins-FPTAS as presented in [3]; the latter turned out to be faster than the TZ-FPTAS of [2]. Martins-FPTAS is based on the classical label setting algorithm for the MOSP problem by [PERSON] [15]. The data structures are similar to those of the MD-FPTAS. Instead of having at most one label per node in the priority queue, it stores all tentative labels therein until they are extracted or deleted because a label entering the queue dominates them. This iteration through the queue to possibly delete labels is more costly than the searches for a node's next candidate label performed in the MD-FPTAS. Table 2 shows the complexity of Martins-FPTAS. ### Test Instances

We perform experiments considering 2 and 3 objective functions. In the biobjective static case we use the same instances that were used in [3]. The first group of such instances consists of graphs that contain only efficient paths. These graphs were first described in [1] and are suitable to check the impact of the used approximation techniques (see Figure 4). \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **TZ [2]** & **Martins-FPTAS [3]** & **MD-FPTAS** &
\begin{tabular}{c} **MD-FPTAS\_T\({}_{v}\)** \\ **(Section 4.2.1)** \\ \end{tabular} \\ \hline \(d=2\) & \(\mathcal{O}\left(\frac{n^{2}m}{\epsilon}\log\left(nC\right)\right)\) & \(\mathcal{O}\left(n^{3}\mathcal{T}^{2}\right)\) & \(\mathcal{O}(\left(n\log n+m\mathcal{T}\right)\mathcal{T})\) & \(\mathcal{O}(\left(n\log n+m\right)\mathcal{T})\) \\ \(d\geq 3\) & \(\mathcal{O}(nm\mathcal{T})\) & \(\mathcal{O}\left(n^{3}\mathcal{T}^{2}\right)\) & \(\mathcal{O}(\left(n\log n+m\mathcal{T}\right)\mathcal{T})\) & \(\mathcal{O}(\left(n\log n+m\mathcal{T}\right)\mathcal{T})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Complexities of the different state of the art FPTAS for MOSP problems. Recall that \(C:=\max_{j\in\{2,\ldots,d\}}\frac{c_{j}^{mn}}{c_{j}^{mn}}\), and \(\mathcal{T}\) denotes the size of the tensors \(T_{v}\), i.e., the max. number of paths to be stored at each node. We call these instances EXP; the corresponding graphs have 3 to 51 nodes. The second group of instances, denoted by GRID, are 33 undirected grid graphs of varying size. All instances within GRID have a number of nodes that varies between 1202 and 40,002 and a number of arcs that varies between 4720 and 159,600. The search starts at an artificial node connected to all nodes in the first column of the grid. The costs on the arcs are generated randomly between 0 and 10. The third group of instances are 15 so called NetMaker graphs. They have 3000 nodes and between 30,000 and 80,000 arcs. The source node is always the node with id 0. Both the GRID and NET instances were first used in [25]. In the 3-dimensional case, we consider a subset of the instances used in [17]. The first set of instances are again NetMaker graphs with an extra cost component. These NET3D instances have 5000 to 15,000 nodes and 40,045 to 344,189 arcs. In total, we consider 35 such graphs. Again, the source node is always the one with id 0. We also consider grids with 3 objectives. The undirected \(100\times 100\) grid graph remains unchanged among all instances; we consider 10 different 3-dimensional arc cost functions. These instances are the only ones for which we consider a One-to-One scenario. Trying to solve the One-to-All MOSP problem on these grids was not possible without violating the time limit. Hence, we added the pruning techniques for One-to-One MOSP instances described in [17] to Algorithm 1. It is easy to see that they are compatible with the approximation techniques used in this paper.