# 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 the dimension \(d\) of the problem is a constant._

Complexity of nextCandidateLabel

For a node \(v\in V\) nextCandidateLabel is called every time a label for \(v\) is made permanent, i.e., \(|L_{v}|+1\) times. The use of the lastProcessedLabel pointers for every arc \((u,v)\in A\) guarantees that the list \(L_{u}\) of permanent labels at each predecessor node \(u\) of \(v\) is traversed exactly once. During each call, a dominance check between the extension along \((u,v)\) of the considered predecessor labels and \(L_{v}\) is performed. This results in a running time of

\[\mathcal{O}\left(\left(\sum_{u\in\delta^{-}(v)}|L_{u}|+|L_{v}|+1\right) \mathcal{C}\right),\]

which summing over all nodes \(v\in V\), can be put as \(\mathcal{O}(m\mathcal{N}_{\max}\mathcal{C})\). Complexity of propagate In total, \(|L_{u}|\) labels are propagated along an arc \((u,v)\in A\). Every time a label is propagated from \(u\) along \((u,v)\), we have to check if the resulting label is dominated by any label in \(L_{v}\). Summing over all nodes, we get an overall complexity of

\[\mathcal{O}\left(\sum_{u\in V}|\delta^{+}(u)||L_{u}|\mathcal{C}\right)= \mathcal{O}(m\mathcal{N}_{\max}\mathcal{C}).\]

Note that since \(Q\) contains at most one label per node, we can have constant time access (e.g., via a pointer) to a node's heap label. We make use of it in Lines 4 and 6 of propagate. Algorithm 1 performs one iteration per permanent label, i.e., \(\mathcal{N}\) iterations in total. In addition to nextCandidateLabel and propagate, a label is extracted in every iteration. All in all, the running time of Algorithm 1 is

\[\mathcal{O}(\mathcal{N}\log n+2m\mathcal{N}_{max}\mathcal{C})=\mathcal{O}( \mathcal{N}\log n+m\mathcal{N}_{max}\mathcal{C})\subseteq\mathcal{O}(\mathcal{ N}_{max}(nlog(n)+m\mathcal{C})). \tag{4}\]

In Table 1, we list the complexity \(\mathcal{C}\) of the dominance check for the different variants of the MD-A that we consider during the paper. It is clear that the space consumption of Algorithm 1 is \(\mathcal{O}(N+m)\) if we assume that \(d\) is fixed. More in depth discussions of these running time bounds for the exact versions of Algorithm 1 can be found in [16; 17]. ## 4 A New FPTAS for the Multiobjective Shortest Path Problem

In this section, we introduce the MD-FPTAS, a new FPTAS for MOSP problems. Basically the MD-FPTAS is Algorithm 1 with a new partial order on the cost vectors, i.e., with a new notion of efficiency. As used for the first time in [2], the main idea is to divide the outcome space into a polynomial number of cells, each of them holding at most one path. The correspondence of a path to a cell is defined via the path's cost vector. For ease of exposition, we will focus on the static version first. In Section 4.1, we show that the FPTAS also works on Dyn-MOSP instances if some extra assumptions are made about the arc cost functions. Consider an \(\alpha\in\mathbb{R}_{\geq 1}^{d}\), and two \((s,v)\)-paths \(p\), \(q\). Then, \(p\)\(\alpha\)-covers \(q\) if \(c_{i}(p)\leq\alpha_{j}c_{j}(q)\) for all \(j\in\{1,\ldots,d\}\). Let \(\mathcal{X}\) be the set of all feasible paths of a (Dyn-)MOSP instance. A subset \(\bar{\mathcal{X}}\subseteq\mathcal{X}\) is an \(\alpha\)-cover of \(\mathcal{X}\) if and only if for any \(x\in\mathcal{X}\) there is a \(\bar{\tau}\in\bar{\mathcal{X}}\) that \(\alpha\)-covers \(x\). If we denote the all-ones vector (initially in \(d\) dimensions) by \(1\), a Fully Polynomial Time Approximation Scheme (FPTAS) for the (Dyn)-MOSP problem is a family of algorithms that computes, for any \(\varepsilon>0\), a \((1+\varepsilon 1)\)-cover of \(\mathcal{X}\). Furthermore, its space requirements and running time are polynomial in the size of the used instance as well as in \(\frac{1}{\varepsilon}\) (note that we could define \(\varepsilon\) as a vector and get different approximation ratios for every component. However, this would not give deeper insights into the used techniques and is also not used in the experiments presented in Section 5).