Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics

The reason that our running time in Theorems 1, 3, and 4, includes $\log \mathrm{\Delta }$ in the exponent is that our algorithm uses the (randomized) hierarchical decomposition of such metrics [32], which produces a decomposition of height $O(\log \mathrm{\Delta }$). A natural question is: why can’t we get rid of the dependence on $\mathrm{\Delta }$ (like [32])? One should note that for most vehicle routing problems on Euclidean or doubling metrics, one can assume that $\mathrm{\Delta }=\text{Poly}(n)$ by a standard scaling of distances at a loss of $(1+\epsilon )$ in approximation factor (for e.g. this has been the first step in [2, 32, 7] for designing approximation schemes for TSP on Euclidean and doubling metrics). This however does not work for budgeted versions (such as orienteering or deadline TSP) as a feasible solution for the scaled version might violate the budget(s) by a $(1+ϵ)$ factor in the original version. In other words, once we scale the distances (by $1+\epsilon$ factor) to reduce to an instance with $\text{Poly}(n)$ distances, a solution in the new instance will not yield a feasible solution in the original as the hard budget constraint (on the total distance) may be violated. Another point worth mentioning is that, although one can get an approximation scheme (with time $n^{O(\text{Polylog}(\mathrm{\Delta }+n)}$) for $k$-path on doubling metrics by embedding them into $\text{Polylog}(\mathrm{\Delta })$-treewidth metrics [33] and using Theorem 2, this will not lead to an approximation scheme for orienteering or deadline TSP as one needs a stronger guarantee, like we obtain in the proof of Theorem 3. Again, this is for the same reason that obtaining a true (and not bicriteria) PTAS for Orienteering on Euclidean metrics [16] required stronger $k$-path algorithms. In general, embedding results cannot be used for budgeted versions of vehicle routing (such as orienteering or deadline TSP).

A natural question is: can’t one extend the known techniques developed for designing PTAS’s for TSP on various metrics (such as planar metrics [28] or doubling metrics [7, 3]) to the setting of orienteering or deadline TSP? It appears the answer is not easy for orienteering and deadline TSP. In general, budgeted versions seem more difficult on any metrics. Extending the ideas of [7] to orienteering or deadline TSP encounters some problems. The very first one (as mentioned above) is the assumption that distances are bounded by $\text{Poly}(n)$ by scaling and losing a $(1+\epsilon )$-factor. This can be done for $k$-path but not in the budgeted settings such as orienteering or deadline TSP. Even if one bypasses this issue, the algorithm of [7] considers tours that are sparse or dense (we have a similar breakdown in our proof). However, for both situations [7] considers (approximate) portal respecting tours. Such tours might have large excess (or regret); so although they will have an approximately optimal overall length, they don’t have the stronger bound (with respect to the excess) needed to obtain a P2P orienteering solution (see [13, 16]). Furthermore, our algorithm for deadline TSP has a step (similar to [20]) that needs to guess a set of vertices whose “excess” (which is defined to be the difference of its visit time in optimum vs. the shortest path distance to the root) is growing geometrically. This requires guessing $\mathrm{\Theta }(\log \mathrm{\Delta })$ many vertices. So overall, there are several obstacles to overcome to turn these algorithms into a PTAS. Nonetheless we hope that ideas developed here (in the proof of Theorem 1) can be used and extended to obtain a PTAS for deadline TSP in doubling or maybe Euclidean metrics.

We start with $P_C$ and whenever an edge $u,v$ of $P_C$ is crossing two parts $C_i,C_j\in {\pi }_C$ that are not portals we replace that edge with a path between $u,v$ via the closest portals in $C_i$ and $C_j$. Consider any edge $u,v$ in $P_C$ that crosses ${\pi }_C$, say $u\in C_i$ and $v\in C_j$. Let $u^{\prime }$ be the nearest portal to $u$ in $S_i$ and $v^{\prime }$ be the nearest portal to $v$ in $S_j$. Replace edge $u,v$ in $P_C$ by the edges $(u,u^{\prime })$, $(u^{\prime },v^{\prime })$, $(v^{\prime },v)$. The increased length incurred is $d(u,u^{\prime })+d(v,v^{\prime })+d(u^{\prime },v^{\prime })-d(u,v)$, which is at most $2d(u,u^{\prime })+2d(v,v^{\prime })$ by triangle inequality. Note that because $S_i$ is a $\beta {\mathrm{\Delta }}_{C_i}$-net of $C_i$ then $d(u,u^{\prime })\le \beta {\mathrm{\Delta }}_{C_i}\le \beta \frac{{\mathrm{\Delta }}_C}{2}$ and $d(v,v^{\prime })\le \beta {\mathrm{\Delta }}_{C_j}\le \beta \frac{{\mathrm{\Delta }}_C}{2}$. Thus the increased length incurred is at most $2\beta {\mathrm{\Delta }}_C$. Recall that for $u,v\in P_C$, the probability that $(u,v)$ crosses ${\pi }_C$ is at most $\delta \kappa \frac{d(u,v)}{{\mathrm{\Delta }}_C}$. Thus in expectation, the increased length of $P_C$ after making it portal respecting with respect to ${\pi }_C$ is at most ${\sum }_{u,v\in P_C}{\kappa }^{\prime }\frac{d(u,v)}{{\mathrm{\Delta }}_C}2\beta {\mathrm{\Delta }}_C={\kappa }^{\prime }\beta \Vert P_C\Vert =\frac{ϵ}{2\delta }\Vert P_C\Vert$. $◀$ Now we formalize the idea of parallel runs of the hierarchical decomposition of Theorem 6. Note that the algorithm for proving Theorem 6 starts from the single cluster $\{V\}$ (as the root of the decomposition) and at each step uses a random partition to the current cluster $C$ to decompose it into $2^{O(\kappa )}$ clusters of diameter half the size. This continues until we arrive at singleton node clusters (leaves of the split-tree). We call one random partition of a cluster $C$ a split operation. The $\gamma$-split-tree hierarchical decomposition of a doubling metric is obtained by considering $\gamma$ random partitions of $C$ (instead of just one) at each step. A $\gamma$-split-tree decomposition has two types of nodes that appear in alternating layers: cluster nodes and split nodes. For each cluster $C$ we have $\gamma$ split nodes in the $\gamma$-split-tree (each corresponding to a random partition of $C$) and these split nodes are all children of $C$. For each split node $s$ that is a child of $C$, it will have children $C_1,\mathrm{\dots },C_{\sigma }$ that are clusters obtained by decomposing $C$ according to the random partition corresponding to $s$. We continue until leaf nodes are cluster nodes with constant size.

Suppose $\mathrm{\Gamma }$ is a $\gamma$-split-tree for $G$ and $\mathrm{\Phi }$ is a partial function from (some) cluster nodes of $\mathrm{\Gamma }$ to one of their split node children with the following properties:

• $\mathrm{■}$

  $\mathrm{\Phi }(C_0)=s$ for some child split node of $C_0$ (where $C_0$ is the root of $\mathrm{\Gamma }$).

• $\mathrm{■}$

  if every ancestor split node of $C$ is in the image of $\mathrm{\Phi }$ then $\mathrm{\Phi }(C)$ is defined.

Note that this function induces a “standard” hierarchical decomposition split-tree as in Theorem 6 as follows: start at the root node $C_0=\{V\}$ of $\mathrm{\Gamma }$ and let root of tree $T$ be $C_0$ and repeat the following procedure: at each step, being at a cluster node $C$ pick $\mathrm{\Phi }(C)$ (a split node child of $C$) and consider the cluster children of $\mathrm{\Phi }(C)$, say $C_1,\mathrm{\dots },C_{\sigma }$, and create nodes corresponding to these as children of $C$ in $T$. Recursively repeat the procedure from each of them. This builds a split-tree tree $T$. We call such a (partial) function $\mathrm{\Phi }$ a determining function for $\mathrm{\Gamma }$ and we say $T$ is induced by $\mathrm{\Phi }$ on $\mathrm{\Gamma }$: $T={\mathrm{\Gamma }|}_{\mathrm{\Phi }}$.

For any cluster $C$ and the split node defined by $\mathrm{\Phi }(C)$, we use $|P^{\ast }\cap E_{{\pi }_{\mathrm{\Phi }(C)}}|$ to denote the number of bridge-edges of $P^{\ast }$ in ${\pi }_{\mathrm{\Phi }(C)}$, i.e. $|P^{\ast }\cap R_{{\pi }_{\mathrm{\Phi }(C)}}|=E_{{\pi }_{\mathrm{\Phi }(C)}}$. Let $\gamma =3\log n$, we can build a $\gamma$-split tree $\mathrm{\Gamma }$ for $G$ in the following way. We start by making $C_0=\{V\}$ to be the root of $\mathrm{\Gamma }$ and iteratively add levels to $\mathrm{\Gamma }$. For a cluster node $C$, we generate its children split nodes as follows: we compute $\gamma$ independent random partitions of $C$, denoted as $\{{\pi }_i\}$, $1\le i\le {\gamma }_i$. Each ${\pi }_i=C_{i,1},\mathrm{\dots },C_{i,{\sigma }_i}$ (where ${\sigma }_i\le 2^{O(\kappa )}$) is obtained by taking a random $\frac{{\mathrm{\Delta }}_C}{4}$-net for $C$. Let $R_{{\pi }_i}$ be the set of bridge-edges of $C$, i.e. edges in $C$ crossing ${\pi }_i$: $R_{{\pi }_i}=\{u,v\in C:u\in C_{i,j},v\in C_{i,j^{\prime }},\text{ for }j\ne j^{\prime }\}$. For each $C_{i,j}$, we further consider the portal set $S_{i,j}$ which is a $\beta {\mathrm{\Delta }}_{C_{i,j}}$-net of it. Let $R_{{\pi }_i}^{\prime }$ be the set of portal edges of $C$: $R_{{\pi }_i}^{\prime }=\{u,v\in C:u\in S_{i,j},v\in S_{i,j^{\prime }},\text{ for }j\ne j^{\prime }\}$. Since $G$ is a doubling metric and $S$ is a net, we find the following bound on the sizes of the portals: $|R_{{\pi }_i}^{\prime }|\le {({\sigma }_i|S_{i,j}|)}^2$ which is bounded by ${(\frac{16{\kappa }^{\prime }\delta }{ϵ})}^{2\kappa }$. We create a child split node $s_i$ for $C$ for each ${\pi }_i$.

For a split node $s$, let $C$ be its parent cluster node and let ${\pi }_i$ be the partition (i.e. the $\frac{{\mathrm{\Delta }}_C}{4}$-net for $C$) corresponding to $s$. Then for each $C_{i,j}\in {\pi }_i$ we create a child cluster node $C_j$ for $s$. The number of the children cluster nodes of $s$ is at most $2^{O(\kappa )}$. We continue this process until each leaf node is a cluster node $C$ with $|C|=O(1)$. From the construction above we know ${\mathrm{\Delta }}_{C_i}\le \frac{{\mathrm{\Delta }}_C}{2}$ if $C_i$ is a child of a split node $s$ which is a child of $C$. Thus there are at most $2\log {\mathrm{\Delta }}_G=2\delta$ levels in $\mathrm{\Gamma }$. If we define the height of $\mathrm{\Gamma }$ as the number of levels of cluster nodes then the height of $\mathrm{\Gamma }$ is at most $\delta$. The branching factor of $\mathrm{\Gamma }$ is then the product of the branching factor of a cluster node and a split node, which is at most $\gamma 2^{O(\kappa )}$. Hence the size of $\mathrm{\Gamma }$ is ${(3\log n{2}^{O(\kappa )})}^{\delta }$. Now we are ready to prove the following structure theorem for a near optimum solution.

Suppose $\mathrm{\Gamma }$ is a $\gamma$-split-tree for $G$. We build $P^{\prime }$ iteratively based on $P^{\ast }$ and at the same time build $\mathrm{\Phi }(\cdot )$ and hence $T$ from the top to bottom.

Initially we set $P^{\prime }$ to be $P^{\ast }$ and start from the root cluster node $C_0$ of $\mathrm{\Gamma }$. At any point when we are at a cluster node $C$ we consider whether $P^{\prime }$ is sparse or dense with respect to $C$:

If $\Vert P^{\prime }\cap C\Vert \le \eta \cdot {\mathrm{\Delta }}_C$, i.e. $P^{\prime }$ is $\eta$-sparse with respect to $C$, we don’t modify $P^{\prime }\cap C$ for when going down from $C$ to any split node $s$ of $C$. Consider any child split node $s$ of $C$ and let ${\pi }_s$ be the partition of $C$ according to the split node $s$. Consider the number of edges of $P^{\prime }\cap C$ that are bridge-edges based on this partition i.e. $|E_{{\pi }_s}|$ (where $E_{{\pi }_s}=P^{\prime }\cap R_{{\pi }_s}$). According to Lemma 9, $𝔼(|P^{\prime }\cap R_{{\pi }_s}|)=𝔼(|E_{{\pi }_s}|)\le {\kappa }^{\prime }\frac{\log n}{ϵ}$. Let the event ${\mathrm{\Lambda }}_s$ be the event that $|P^{\prime }\cap R_{{\pi }_s}|\le 2{\kappa }^{\prime }\frac{\log n}{ϵ}$. By Markov inequality $\mathrm{Pr}[{\mathrm{\Lambda }}_s]\ge \frac{1}{2}$. Recall there are $\gamma =3\log n$ many children split nodes of $c$, i.e. $\gamma$ independent random partitions of $C$. Thus the probability that for at least one child split node $s$ of $c$, event ${\mathrm{\Lambda }}_s$ holds is at least $1-{(1-\frac{1}{2})}^{3\log n}\ge 1-\frac{1}{n^3}$. In this case we select split node $s$ and define $\mathrm{\Phi }(C)=s$ and consider each cluster child node of $s$ iteratively ($P^{\prime }$ has not changed in this step).

Suppose $P^{\prime }$ is $\eta$-dense with respect to $C$. Consider an arbitrary split child $s$ of $C$. We will modify $P^{\prime }$ going down the split node $s$ to be portal respecting with respect to ${\pi }_s$ as described in Lemma 11. Assume ${\pi }_s=C_1,\mathrm{\dots },C_{\sigma }$. For each $C_i$ let $S_i$ be a set of portals. If we go down the split node $s$ we modify $P^{\prime }$ to be portal-respecting for each $C_i$. Note that the set of edges $P^{\prime }$ crossing ${\pi }_s$ after making it portal respecting with respect to ${\pi }_s$ is a subset of $R_{{\pi }_s}^{\prime }$. Thus $|P^{\prime }\cap R_{{\pi }_s}^{\prime }|$ is at most $|R_{{\pi }_s}^{\prime }|$ which is at most ${(\frac{16{\kappa }^{\prime }\delta }{ϵ})}^{2\kappa }$ in this case. According to Lemma 11, the expected increase of length of $P^{\prime }$ after making it portal respecting with respect to ${\pi }_s$ is at most $\frac{ϵ}{2\delta }\Vert P^{\prime }\cap C\Vert$. Let ${\mathrm{\Lambda }}_s^{\prime }$ be the event that the increase of length of $P^{\prime }$ after making it portal respecting with respect to ${\pi }_s$ is at most $\frac{ϵ}{\delta }\Vert P^{\prime }\cap C\Vert$. By Markov inequality, $\mathrm{Pr}[{\mathrm{\Lambda }}_s^{\prime }]\ge \frac{1}{2}$. Recall there are $\gamma$ many children split nodes of $C$. Thus the probability that for at least one child split node $s$ of $C$ we have ${\mathrm{\Lambda }}_s^{\prime }$ is at least $1-{(1-\frac{1}{2})}^{3\log n}\ge 1-\frac{1}{n^3}$. In this case we set $\mathrm{\Phi }(C)=s$ for this particular split node $s$ for which ${\mathrm{\Lambda }}_s^{\prime }$ happens.

Therefore, regardless of whether $P^{\prime }$ is sparse or dense w.r.t. $C$, such $s$ exists for cluster $C$ with the probability at least $1-\frac{2}{n^3}$ and we can define $\mathrm{\Phi }(C)$. Once we have $\mathrm{\Phi }(.)$ defined for clusters at a level of $\mathrm{\Gamma }$, we have determined the clusters at the same level of $T={\mathrm{\Gamma }|}_{\mathrm{\Phi }}$. Note there are at most $n$ cluster nodes in one level of $T$. Thus with probability at least $1-\frac{2}{n^2}$ such split nodes exist for all cluster nodes in one level. Since height of $\mathrm{\Gamma }$ (and $T$) is $\delta$, thus with probability at least ${(1-\frac{2}{n^2})}^{\delta }\ge 1-\frac{1}{n}$ (assuming that $\delta$ is polylogarithmic in $n$) such $\mathrm{\Phi }(.)$ is well defined over all levels. Note the increase of length of $P^{\prime }$ only occurs when $P^{\prime }$ is $\eta$-dense with respect to $C$ and for any of these clusters $C$ in ${\mathrm{\Gamma }|}_{\mathrm{\Phi }}$, the increase of length $P^{\prime }$ by modifying $P^{\prime }$ to be portal respecting with respect to ${\pi }_{\mathrm{\Phi }(C)}$ is at most $\frac{\epsilon }{\delta }\Vert P^{\prime }\cap C\Vert$. Since this $(1+\frac{\epsilon }{\delta })$-factor increase occurs each time we go down the decomposition form a cluster $C$ to the next cluster level down, and the height of the decomposition is $\delta$, thus inductively, for any cluster $C$ in ${\mathrm{\Gamma }|}_{\mathrm{\Phi }}$: $\Vert P^{\prime }\cap C\Vert \le {(1+\frac{ϵ}{\delta })}^{\delta }\Vert P^{\ast }\cap C\Vert \le e^{ϵ}\Vert P^{\ast }\cap C\Vert \le (1+{ϵ}^{\prime })\Vert P^{\ast }\cap C\Vert$ for some ${\epsilon }^{\prime }>0$ depending on $\epsilon$. Replacing $ϵ$ with ${\epsilon }^{\prime }$ we get $\Vert P^{\prime }\cap C\Vert \le (1+ϵ)\Vert P^{\ast }\cap C\Vert$. $◀$

Intuitively, this is saying if $Q$ passes through several (disjoint) clusters in $D$ then the excess of $Q$ is at least as big as sum of excess of $Q$ in those clusters.

Suppose start-end node of $Q$ are $u,v$ and let $Q_0$ be the path just consisting of $u,v$. By definition of the excess, ${ℰ}_{Q,2}=\Vert Q\Vert -\Vert Q_0\Vert$. Now consider following path $Q^{\prime }$, which starts at $u$ and follows $Q$ but when it encounters a cluster $C$ in $D$ and it visits $C$ for the first time it directly connects the start and end node of the subpath of $Q$ in $C$. When it encounters a cluster $C$ in $D$ that is visited before, then bypasses $C$ entirely, i.e. directly connects the last vertex in $Q$ before it enters $C$ this time and the first vertex in $Q$ after it visits after it exits $C$ this time. From the construction of $Q^{\prime }$, if $C\in D$, then $\Vert Q^{\prime }\cap C\Vert \le {\mathrm{\Delta }}_C$. Clearly for any cluster $C\notin D$: $\Vert Q^{\prime }\cap C\Vert =\Vert Q\cap C\Vert$. Thus ${ℰ}_{Q,2}=\Vert Q\Vert -\Vert Q_0\Vert \ge \Vert Q\Vert -\Vert Q^{\prime }\Vert ={\sum }_{C\in D}(\Vert Q\cap C\Vert -\Vert Q^{\prime }\cap C\Vert )\ge {\sum }_{C\in D}(\Vert Q\cap C\Vert -{\mathrm{\Delta }}_C)$. $◀$

Note that in the proof of Theorem 13, the increase of length of $P^{\prime }$ only occurs when $P^{\prime }$ is $\eta$-dense with respect to a cluster $C$. We generate a set of disjoint clusters $D$ in $T={\mathrm{\Gamma }|}_{\mathrm{\Phi }}$: we start from $C_0$ (the root of $T$) to generate $D$ iteratively. If $P^{\prime }$ is $\eta$-dense with respect to $C$ then add $C$ to $D$, if $P^{\prime }$ is $\eta$-sprase with respect to $C$ and $C$ is a non-leaf cluster node then iteratively consider all children cluster nodes of $C$. Let $D$ be the set of cluster nodes returned by this process. From the construction of $D$, clusters in $D$ are disjoint, and for each cluster $C\in D$, $P^{\prime }$ is $\eta$-dense with respect to $C$ and $\Vert P^{\prime }\Vert -\Vert P^{\ast }\Vert ={\sum }_{C\in D}(\Vert P^{\prime }\cap C\Vert -\Vert P^{\ast }\cap C\Vert )$.

Let $\{v_1,\mathrm{\cdots },v_{\mu }\}$ be the optimal $\mu$-jump of $P^{\ast }$ and let $P_1^{\ast },P_2^{\ast },\mathrm{\cdots },P_{\mu -1}^{\ast }$ be the subpaths divided by the vertices in this $\mu$-jump, i.e. $P_i^{\ast }$ is the subpath of $P^{\ast }$ whose start and end are $v_i$ and $v_{i+1}$, respectively. By definition of excess, ${ℰ}_{P^{\ast },\mu }={\sum }_{i=1}^{\mu -1}{ℰ}_{P_i^{\ast },2}$. For the set $D$ and each $P_i^{\ast }$, by Lemma 14, ${ℰ}_{P_i^{\ast },2}\ge {\sum }_{C\in D}(\Vert P_i^{\ast }\cap C\Vert -{\mathrm{\Delta }}_C)$. Thus ${ℰ}_{P^{\ast },\mu }\ge {\sum }_{i=1}^{\mu -1}{\sum }_{C\in D}(\Vert P_i^{\ast }\cap C\Vert -{\mathrm{\Delta }}_C)$, which is ${\sum }_{C\in D}(\Vert P^{\ast }\cap C\Vert -(\mu -1){\mathrm{\Delta }}_C)$. Recall from the proof of Theorem 13 that we modify $P^{\prime }$ when it is $\eta$-dense with respect to $C$ (i.e. $\Vert P^{\prime }\cap C\Vert >\frac{\log n}{\epsilon }{\mathrm{\Delta }}_C$) and we always have $\Vert P^{\prime }\cap C\Vert \le (1+\epsilon )\Vert P^{\ast }\cap C\Vert$, which implies $\Vert P^{\ast }\cap C\Vert \ge \frac{\log n}{ϵ(1+\epsilon )}{\mathrm{\Delta }}_C$; in a sense $P^{\ast }$ is also (almost) $\eta$-dense with respect to $C$. Since $\mu =\lceil \frac{1}{ϵ}\rceil +1$, thus $\Vert P^{\ast }\cap C\Vert -(\mu -1){\mathrm{\Delta }}_C\ge \frac{\Vert P^{\ast }\cap C\Vert }{2\epsilon }$ and ${ℰ}_{P^{\ast },\mu }\ge {\sum }_{C\in D}\frac{\Vert P^{\ast }\cap C\Vert }{2\epsilon }$.

As in the proof Theorem 13, for any cluster $C\in T$, $\Vert P^{\prime }\cap C\Vert \le (1+ϵ)\Vert P^{\ast }\cap C\Vert$. Thus $\Vert P^{\prime }\Vert -\Vert P^{\ast }\Vert ={\sum }_{C\in D}(\Vert P^{\prime }\cap C\Vert -\Vert P^{\ast }\cap C\Vert )\le {\sum }_{C\in D}ϵ\Vert P^{\ast }\cap C\Vert \le 2{ϵ}^2{ℰ}_{P^{\ast },\mu }\le \epsilon {ℰ}_{P^{\ast },\mu }$. $◀$

We should note that we can generalize this proof slightly as follows. Suppose that we pick some arbitrary $\mu$-jump of $P^{\ast }$ (instead of the optimum) and consider ${\tilde{P}}_1^{\ast },\mathrm{\dots },{\tilde{P}}_{\mu -1}^{\ast }$ which are the subpaths of $P^{\ast }$ defined by that $\mu$-jump. Then the same arguments show that ${\sum }_{i=1}^{\mu -1}{ℰ}_{{\tilde{P}}_i^{\ast },2}\ge {\sum }_{i=1}^{\mu -1}{\sum }_{C\in D}(\Vert {\tilde{P}}_i^{\ast }\cap C\Vert -{\mathrm{\Delta }}_C)={\sum }_{C\in D}\Vert P^{\ast }\cap C\Vert -(\mu -1){\mathrm{\Delta }}_C$ which implies ${\sum }_{i=1}^{\mu -1}{ℰ}_{{\tilde{P}}_i^{\ast },2}\ge {\sum }_{C\in D}\frac{\Vert P^{\ast }\cap C\Vert }{2}$. Using this one can show that at the end $\Vert P^{\prime }\Vert \le \Vert P^{\ast }\Vert +\epsilon {\sum }_{i=1}^{\mu -1}{ℰ}_{{\tilde{P}}_i^{\ast },2}$. This slightly more general version will be used later when designing our algorithm for deadline TSP.