# An FPTAS for Dynamic Multiobjective Shortest Path Problems
## 3 The Multiobjective Dijkstra Algorithm for Dynamic MOSP Problems
### Description of the Algorithm
For the \((s,v)\)-path \(\tilde{p}\) corresponding to \(\tilde{\ell}\), we have

\[c(\tilde{p})=c(\tilde{p}_{u})+c_{(u,v)}\overset{Equation(\ref{eq:p})}{\leq}r^ {k-1}c(p^{*}_{u})+c_{(u,v)}\leq r^{k-1}c(p^{*}). \tag{8}\]

From the proof of the base case and from Lemma 2, we know that \(\tilde{\ell}\) is going to either be made permanent in a later iteration or be discarded. In case \(\tilde{\ell}\) is made permanent, we have \(c(\tilde{p})\leq r^{k-1}c(p^{*})\leq r^{k}c(p^{*})\) and we are done. If \(\tilde{\ell}\) is discarded, there exists a permanent label \(\ell\in L_{v}\) corresponding to an \((s,v)\)-path \(p\) such that \(c_{1}(p)\leq c_{1}(\tilde{p})\) and \(\text{pos}(p)\leq\text{pos}(\tilde{p})\). The latter inequality implies \(c_{j}(p)\leq rc_{j}(\tilde{p})\) for \(j\in\{2,\ldots,d\}\) and, for \(j=1\), \(c_{1}(p)\leq rc_{1}(\tilde{p})\) is trivially given. Combining this with Euqation (8), we get

\[\frac{1}{r}c(p)\leq c(\tilde{p})\leq r^{k-1}c(p^{*})\Longleftrightarrow c(p) \leq r^{k}c(p^{*}),\]

which finishes the proof. ### FPTAS for Dyn-MOSP Problems

From now on we restrict the set \(\mathbb{F}\) of arc cost functions in Dyn-MOSP instances to contain only continuous, piecewise linear FIFO functions. In this case, the proof of Theorem 1 works if the intercepts of the affine functions describing the pieces of the arc cost functions are non-negative. Note that in the proof of Theorem 1 we needed the arc cost vectors only in Equation (8). Using the notation for dynamic cost, what needs to hold is

\[c(\tilde{p})=c(\tilde{p}_{u})+c_{(u,v)}(\tilde{p}_{u})\overset{!}{\leq}r^{k-1 }c(p^{*}_{u})+r^{k-1}c_{(u,v)}(p^{*}_{u})=r^{k-1}c(p^{*}). \tag{9}\]To prove the following Lemma, we consider a function \(f\in\mathbb{F}\) with \(k\in\mathbb{N}\) breakpoints and describe the affine functions that build the pieces of \(f\) by \(\operatorname{aff}_{i}(x):=a_{i}x+b_{i}\), \(i\in\{1,\ldots,k-1\}\). Lemma 3: _Let \(f\in\mathbb{F}\) be a piecewise affine function with \(k\in\mathbb{N}\) breakpoints and \(\alpha\in\mathbb{R}_{>1}\) a constant. Then, for points \(x\), \(y\in\mathbb{R}_{\geq 0}\) with \(x\leq\) any there holds \(x+f(x)\leq\alpha(y+f(y))\) if the intercepts \(b_{i}\) of the affine functions building \(f\) are non-negative for all \(i\in\{1,\ldots,k-1\}\)._

Proof: We consider three different cases to prove the statement. Case 1: \(f(x)\leq f(y)\). Since \(\alpha>1\), we have \(f(x)\leq\alpha f(y)\). Together with \(x\leq\alpha y\) this proves the statement. Case 2: \(x<y\) and \(f(x)\geq f(y)\). In this case, the FIFO property and \(\alpha>1\) can be used to get:

\[x+f(x)\leq y+f(y)\leq\alpha y+\alpha f(y).\]

Case 3: \(y<x\) and \(f(x)>f(y)\). Let \(\operatorname{aff}_{i}\) be the affine function with \(\operatorname{aff}_{i}(y)=f(y)\) and \(\operatorname{aff}_{j}\) the one with \(\operatorname{aff}_{j}(x)=f(x)\). There holds \(i\leq j\) and we define \(\operatorname{aff}_{l}\), \(l\in\{i,\ldots,j\}\), to be the affine function corresponding to the steepest piece of \(f\) between \(y\) and \(x\), i.e., the one with the biggest \(a_{l}\). This choice implies \(f(x)\leq\operatorname{aff}_{l}(x)\) and \(\operatorname{aff}_{l}(y)\leq f(y)\). Additionally, as for any affine function with positive intercept we have \(\operatorname{aff}_{l}(\alpha y)\leq\alpha(a_{l}y+b_{l})=\alpha\operatorname{ aff}_{l}(y)\). All in all, we can conclude

\[f(x)\leq\operatorname{aff}_{l}(x)\leq\operatorname{aff}_{l}(\alpha y)\leq \alpha\operatorname{aff}_{l}(y)\leq\alpha f(y).\]

Together with \(x\leq\alpha y\) this proves the statement. Now we set \(c_{(u,v),j}=f\), \(c_{j}(\bar{p})=x\), \(c_{j}(p^{*})=y\), and \(r^{k-1}=\alpha\) to get that Equation (9) holds under the given assumptions. This enables us to formulate our main Theorem:

Theorem 4.2 (FPTAS for Dyn-MOSP problems): _Let \(\mathcal{I}\) be a Dyn-MOSP instance with continuous piecewise linear and positive arc cost functions that fulfill the FIFO property.