Proof. Let \(l > 0\) and \(v \in S'\) be a request such that \(d(u,v) \leq l\). We have \(|t(v) - t(u)| \leq d(u,v) \leq l\). This implies that the arrival time \(t(v)\) satisfies \(t(v) \leq t(u) + d(u,v) \leq t(u) + l\). ◻

Proof. Our proof relies on a lemma used to analyze TSP heuristics by Rosenkrantz et al [17]:

Let \(p \in V\), we consider \(q \in V\) the node matched with \(p\) in \(M\). We set \(l_p = l_q = g(p,q)\) the length of the matched edge. Let us show that this definition satisfies the requirements of 3:

• Let \(p,q\) be two distinct nodes in \(G\). Without loss of generality, let us assume that GREEDY matched \(p\) before \(q\) (if they got matched together any order is fine). Because right before \(p\) was matched, both \(p\) and \(q\) were unmatched and the greedy takes the unmatched edge of smallest weight, it means that the edge used to match \(p\) has weight at most \(g(p,q)\). Therefore \(g(p,q) \geq l_p \geq \min(l_p, l_q)\).

• Let \(p \in V\), we assume \(p\) got matched to some \(q \in V\), so \(l_p = g(p,q)\). The TSP consists of two paths between \(p\) and \(q\). Given that we are in a metric graph, we get \(OPT_{TSP} \geq 2 g(p,q)\) and therefore \(l_p \leq \frac{1}{2} OPT_{TSP}\)

We can thus apply 3 on \((l_p)\): \[\begin{align} \sum l_p \leq \frac{1}{2}(\lceil \log n \rceil + 1) OPT_{TSP} \end{align}\] We remark that by the definition of \((l_p)\), the weight of every matched edge appears exactly twice (one for each endpoint) in \((l_p)\), therefore \(\sum l_p = 2 w(M)\). The theorem follows from the last two equations. ◻

Proof. We first remark that each component starts by containing a single request and each merge decreases the total number of components by at least one. Therefore, because there are in total \(m\) requests, there can always be at most \(m-1\) merges during the whole execution of the algorithm. So the main loop of ONLINE_MATCHING, which performs an additional iteration every time a merge happens, will never loop infinitely. In a similar way, the loop of the NEARBY_FIXUP procedure, which contains a special merge in its body, cannot iterate infinitely. These are the only two loops our algorithm has. ◻

Proof. We first notice that assuming its input contains an even number of requests, the greedy algorithm produces a perfect matching within a finite amount of time. Let \(t_{max}\) the maximal time of arrival of a request in the greedy input. Let \(d_{max}\) the maximal distance between two requests in the greedy input. Then at time \(t_{max} + 2d_{max}\), the algorithm would immediately match in pairs any requests not matched yet. Moreover, once two requests have been matched, they are not considered anymore. Therefore, by time \(t_{max} + 2d_{max}\), the greedy algorithm computes a perfect matching.

Looking at the overall algorithm, we note that it adds two requests to the greedy at a time, this ensures that the input of any greedy instance will only contain an even amount of requests. Therefore, all requests in an even component will be part of a greedy instance and odd components will have exactly one request not part of a greedy instance. It thus suffices to prove that some time after all requests arrive, there will be only even components remaining to conclude.

As shown in the previous proof, the total number of merges the algorithm can perform is at most \(m - 1\), so finite. Thus, we can find some time \(t_{end}\) after all requests arrived such that the component structure does not change afterwards. We also consider \(t_{last} \leq t_{end}\) the last arrival time of a request.

Let us assume that after \(t_{end}\), there is still at least one odd component. We note that the parity of \(m\) must be the same as the number of odd components. Because \(m\) is even, there must be an even number of odd components. Because there is at least one odd component, it means there are at least two such components. Let \(C_1\) be the odd component with minimum rank and let \(C_2\) be any other odd component. We note that a component can only wait on an odd component with strictly lower rank, therefore \(C_1\) cannot wait on another component. Let \(l = d(C_1, C_2)\), using 2, \(l \geq D(C_1, C_2)\). Therefore after \(t_{end}\) and by time \(t_{last} + 2l\), we are guaranteed the algorithm will merge \(C_1\) to its nearest compatible component, being \(C_2\) or some other component. This is a contradiction because we assumed no merge happened after \(t_{end}\). Therefore, there are no odd components remaining after \(t_{end}\) and all even components will have a perfect matching done over their requests within a finite amount of time. This concludes the proof. ◻

Proof. The proof is done by induction. When a request arrives, a component of rank \(0\) is created for it, which satisfies the property. Subsequently, the rank of a component can only be increased in two ways. The first one is when two components of rank \(r\) merge in the combining step, causing the resulting component to have rank \(r+1\). The second one is in the pruning step, which happens when we have two components in one tree with the same rank \(r\). These get merged together to get a component of rank \(r+1\). In both cases, a component of rank \(r+1\) is formed by a merge containing at least two components of rank \(r\). Hence, the claim follows immediately by induction. ◻

Proof. We consider the three different cases where a regular merge happens:

• In the combining step, with \(C_1\) and \(C_2\). By definition \(C_2\) is indeed the closest compatible component to \(C_1\). In the first case we have \(r = \text{nrank}(C_2) > \text{rank}(C_1)\). In the second case, we have \(r = \text{rank}(C_2) \geq \text{rank}(C_1)\). Moreover, in the latter case, if \(\text{rank}(C_2)\) was equal to \(\text{rank}(C_1)\), it gets incremented, therefore \(r > \text{rank}(C_1)\).

• In the pruning step, along edges of the waiting tree. But by definition, for a waiting edge \(C_A \rightarrow C_B\) to exist, \(C_B\) must be the closest compatible component to \(C_A\). Moreover, a regular merge is only called with components from \(H\), which by definition have rank at most \(\text{rank}(C_1)\) while \(r = \text{rank}(C_1) + 1\) which therefore satisfy the property.

 ◻

Proof. We first consider the time a component is given a non-\(\bot\) nearby rank, we can find components \(C_{from}\), \(C_{to}\) and a rank \(r\) such that it happens in the regular merge from \(C_{from}\) to \(C_{to}\) at rank \(r\). Using 2, \(C_{to}\) is the closest compatible component to \(C_{from}\). If a component \(C\) gets its nearby rank modified by this part of the algorithm, it implies that it is in \(H\) and therefore that \(D(C_{from}, C) < D(C_{from}, C_{to}) / (\text{rank}(C_{from}) + 2) \leq D(C_{from}, C_{to})\). By minimality of \(C_{to}\), it implies that \(C\) is not compatible with \(C_{from}\). Therefore, \(C\) is an even component and \(\text{rank}(C) < \text{rank}(C_{from})\). Using 2 again, we get that \(\text{rank}(C_{from}) < r\), which proves that \(\text{rank}(C) < r = \text{nrank}(C)\).

We claim that if any component merges into \(C\), then it immediately merges into a higher rank component. Indeed, because \(C\) is even, no component can merge into it in the pruning step as waiting edges are only between odd components. Moreover, in the combining, given that \(C\) is even, for it to be compatible with \(C_1\), either its nearby rank is at least \(\text{rank}(C_1) + 1\) or its rank is at least \(\text{rank}(C_1)\) in which case its nearby rank is also at least \(\text{rank}(C_1) + 1\). Therefore, the nearby fixup procedure gets called and \(C\) gets eventually merged into a component of rank at least its nearby rank. This proves that as soon as a component is given a non-\(\bot\) nearby rank, it stays as an even component and its rank never increases. ◻

Proof. Special merges are only used at two locations in our algorithm. The first one is within the combining step, to merge component \(C_3\) into \(C_1\). We remark that \(C_3 \in H\), therefore \(D(C_1, C_3) < D(C_1, C_2)\). Because \(C_2\) is the closest compatible component to \(C_1\), it means that \(C_3\) is not compatible with \(C_1\), which implies that \(\text{rank}(C_3) < \text{rank}(C_1)\) and \(\text{rank}(C_1)\) is the rank used for the special merge, which proves the lemma in this case. Moreover, all even components on the shortest path from \(C_1\) to \(C_3\) are also not compatible with \(C_1\), therefore their ranks are also strictly less than \(\text{rank}(C_1)\). The other location is in the nearby fixup procedure, where \(C_1\) is merged into \(C_2\) with rank \(r = \max(\text{rank}(C_2), \text{nrank}(C_2))\). We remark that we chose \(C_2\) such that its rank or nearby rank is at least \(\text{nrank}(C_1)\), i.e \(r \geq \text{nrank}(C_1)\). Using 3, \(r \geq \text{nrank}(C_1) > \text{rank}(C_1)\), which proves the first point. Regarding even components on the path from \(C_1\) to \(C_2\), the fixup procedure did not consider them, thus their rank must be strictly less than \(\text{nrank}(C_1) \leq r\), this satisfies the second point. ◻

Proof. The property \(r > \text{rank}(C_{from})\) is a direct consequence of 2 4. Moreover, 2 proves that components in \(D\) are not compatible with \(C_{from}\), so their rank is less than \(\text{rank}(C_{from})\). Meanwhile, 4 directly proves that \(r > \max_{C \in D} \text{rank}(C)\) for special merges. We now prove that \(r \geq \text{rank}(C_{to})\).

For regular merges, in the combining step, the rank used is either \(\text{rank}(C_{to})\) or \(\text{nrank}(C_{to})\) which using 3 is at least \(\text{rank}(C_{to})\). In the pruning step, the rank used is \(\text{rank}(C_1) + 1\), which is the rank of \(C_{to} = C_3\). For special merges, the rank used is either \(\text{rank}(C_{to})\) or \(\max(\text{rank}(C_{to}), \text{nrank}(C_{to}))\), which satisfies the property. ◻

Proof. We consider the different locations in the algorithm where these merges happen. For most of these cases, this is done with \(r = \text{rank}(C_{to})\) which implies this property. The only exception is in the combining step, where a regular merge is done with rank \(\text{nrank}(C_{to})\). However, right after, the fixup procedure keeps merging \(C_{to}\) until it reaches a component of rank at least \(\text{nrank}(C_{to})\), which satisfies this property. ◻

Proof. We first remark that 5 6 show that the rank of a component is only increasing: if at some time \(t\) a component of rank \(r\) exists, then at any time \(t' \geq t\), we are guaranteed that a component of rank \(r' \geq r\) will exist.

We now consider the fixup procedure. We have \(\text{nrank}(C_1) \neq \bot\). \(C_1\) was given its nearby rank by a previous regular merge of rank \(\text{nrank}(C_1)\). Using the previous observation and 6, it means there exists a component \(C'\) of rank at least \(\text{nrank}(C_1)\). Moreover, using 3, we have \(\text{rank}(C_1) < \text{nrank}(C_1)\), therefore \(C_1 \ne C'\). Thus, there always exists at least one other component with rank at least \(\text{nrank}(C_1)\), so the assumptions made by the fixup procedure hold. ◻

Proof. Because edges are only added inside a merge procedure, this is a direct consequence of 5 6. ◻

Proof. We first claim that when doing a regular or special merge, one of the two endpoints is an odd component. Indeed, in the combining step, one of \(C_{from}\) or \(C_{to}\) is always \(C_1\) which is an odd component. When doing the nearby fixup procedure, we keep merging \(C_1\) which originally was odd to a component \(C_2\) until the nearby rank of \(C_2\) is \(\bot\). Because of 3, components with a non-\(\bot\) nearby rank are always even, so we keep merging an odd component to an even component, which results in an odd component. In the pruning step, we observe that any component in the waiting tree is odd, so all merges follows this property.

We now prove this lemma by induction on the time of the last merge operation. We consider a component \(C\) at some time \(t\) right after its last merge operation. If the component never had a merge, it means it has rank \(0\), and is therefore a singleton. The request it contains immediately satisfies the property. Otherwise, assume this property is satisfied by all components until the previous merge. As stated above, one of the two components during this merge is an odd component \(C'\), with rank at most \(rank(C)\). Therefore, using the property on \(C'\), we can find a request \(v\) which always has been inside an odd component up to this point. Whether \(C\) is odd or even, \(v\) satisfies the desired property for \(C\). ◻

Proof. We remark that if \(C\) gets merged into a component of rank at least \(\text{nrank}(C)\), then using 7, all edges added after this time will have rank at least \(\text{nrank}(C)\). Therefore, we only need to consider edges added before \(C\) gets merged into a component with such rank.

We first consider the case where \(C\) gets merged as an even component on the path between \(C_{from}\) and \(C_{to}\) for a regular merge. This implies that \(C\) is not compatible with \(C_{from}\), so \(\text{nrank}(C) \leq \text{rank}(C_{from})\). Because of 2, the edge rank is strictly more than \(\text{rank}(C_{from})\), which satisfies our requirement. If a special merge is done inside the combining step, then \(C\) is not compatible with \(C_{to}\) which using the same argument as before implies that the edges added have rank at least \(\text{nrank}(C)\). Because \(C\) is even, it cannot be the first endpoint for a merge in the combining step or any endpoint for a merge in the pruning step because all endpoints are odd components. Because of 3, we have \(\text{nrank}(C) > \text{rank}(C)\), therefore a merge can only happen with \(C\) as \(C_{to}\), and either right before the nearby fixup procedure, for which the edge rank is at least \(\text{nrank}(C)\) or inside the nearby fixup, for which the edge rank is also at least \(\text{nrank}(C)\). This completes the proof. ◻

Proof. We note that all regular or special edges we add are part of the shortest path (according to \(D\)) between two distinct components. As a consequence, no cycles are introduced when adding regular or special edges. ◻

Proof. This is a direct consequence of 7 2. ◻

Proof. An edge is part of \(R_i\) if it was added by a regular merge from some component \(C_{from}\) to \(C_{to}\) with rank \(i\). Let \(A\) be the set of all components which were used as \(C_{from}\) for a regular merge of rank \(i\). We remark, using 2, that all components in \(A\) are odd and have rank strictly less than \(i\). Moreover, after this merge, they are part of a component of rank at least \(i\), therefore all components in \(A\) are disjoint (by which we mean the set of vertices of each component are disjoint). Furthermore, using 9, every component in \(A\) exactly matches one component in \(\mathfrak{D}_{i-1}\), i.e \(A \subseteq \mathfrak{D}_{i-1}\).

For every component \(C \in A\), we note \(r_C\) the compressed distance from \(C\) to the closest odd component in \(\mathfrak{D}_{i-1}\). Moreover, we note \(l_C\) the total weight of the edges of rank \(i\) added from the regular merge with source \(C\) and rank \(i\). We note because of 2 that \(l_C\) is the compressed distance from \(C\) to the closest compatible component at the time of merging. We have: \[\begin{align} w(R_i) = \sum_{C \in A} l_C \end{align}\] Moreover, using [lemma:decomp-shortest-opt], we get: \[\begin{align} \sum_{C \in A} r_C \leq 2 OPT \end{align}\]

Let \(C \in A\), we want to prove that \(l_C \leq (i+1) \cdot r_C\) which will conclude the proof. Let \(H\) be the set of components whose compressed distance was strictly less than \(l_C / (i + 1)\) at the time of merging. Because their compressed distance is strictly less than \(l_C\), it implies they were not compatible with \(C\) and therefore are even and of rank strictly less than \(\text{rank}(C)\). Moreover, during the regular merge, their nearby rank is set to be at least \(i\). Finally, by design of the algorithm, we note that the maximum arrival time of any request in \(H\) is at most \(t_{max}(C) + l_C\).

We want to prove that all components within compressed distance \(l_C / (i + 1)\) of \(C\) in \(\mathfrak{D}_{i-1}\) are even, this would imply that \(r_C\), the shortest distance from \(C\) to another odd component in \(\mathfrak{D}_{i-1}\) is at least \(l_C / (i + 1)\) away from \(C\). Because the algorithm assigns all components in \(H\) a nearby rank of at least \(i\), 7 2 implies that components in \(H\) have exactly matching components in \(\mathfrak{D}_{i-1}\), which are therefore also even. We consider the shortest path between \(C\) and its closest odd component in \(\mathfrak{D}_{i-1}\), which has weight \(r_C\). Let us consider the first edge along this path between a component in \(\{C\}\cup H\) and a component outside of \(\{C\}\cup H\). \(P\) starts from \(C\) and ends with an odd component different from \(C\). Given that \(H\) contains only even components, \(P\) ends in a component not in \(\{C\}\cup H\), so such an edge \(e\) always exists. Let \(e = (u,v)\), with \(u\) being a request in \(\{C\}\cup H\) and \(v\) being a request outside of it. We have two cases:

• Request \(v\) has already arrived when \(C\) merged. Let \(C'\) be the component \(v\) belonged to when \(C\) merged. Because \(v\) is not a request in \(H\), this means that \(C' \notin H\) and by definition of \(H\), at the time of merge, \(D(C, C') \geq l_C / (i+1)\). However, we observe that the prefix of \(P\) until \(v\) is a path from \(C\) to a request in \(C'\) which only goes through components in \(H\), which existed at the time of merge and were even. So by definition, this prefix of \(P\) must have weight at least \(l_C / (i+1)\), so \(w(P) \geq l_C / (i + 1)\).

• Request \(v\) arrived after \(C\) merged. Let \(t_{merge}\) be the time when \(C\) merged. By design of the algorithm, we know that \(t_{merge} \geq t_{max}(C) + 2l_C\). Moreover, using 2, \(\text{rank}(C) < i\), so all components \(C' \in H\) verify \(D(C,C') < l_C / (\text{rank}(C) + 2)\). As a consequence, the algorithm ensured in the combining step that all components \(C' \in H\) satisfy \(t_{max}(C') \leq t_{max}(C) + l_C\). Therefore: \[\begin{align} w(e) &= d(u,v) \\* & \geq |t(v) - t(u)| \\ &= t(v) - t(u) \\ &\geq t_{merge} - \max (t_{max}(C), \max_{C' \in H} t_{max}(C')) \\ &\geq t_{max}(C) + 2l_C - (t_{max}(C) + l_C) \\ &\geq l_C \end{align}\] Therefore, \(w(P) \geq w(e) \geq l_C \geq l_C / (i + 1)\)

In both cases, \(r_C = w(P) \geq l_C / (i + 1)\), therefore \(l_C \leq (i+1) \cdot r_C\) and: \[\begin{align} w(R_i) &= \sum_{C \in A} l_C \\ & \leq \sum_{C \in A} (i+1)\cdot r_C \\ & = (i+1) \cdot \sum_{C \in A} r_C \\ & \leq (i+1)\cdot 2OPT \end{align}\] ◻

Proof. Let \(i \in [\![1, \lfloor \log m\rfloor ]\!]\), let \(A = \mathcal{F}'_{i-1} \cup R_i \subseteq \mathcal{F}\). We consider a special merge from \(C_{from}\) to \(C_{to}\) which contributes a path \(P\), being a shortest path from \(C_{from}\) to \(C_{to}\), to \(S'_i\). Let \(D\) be the set of even components merged along \(P\) (excluding endpoints). We want to prove two properties: (i) the edges of \(T(C_{from})\) and the spanning trees of components in \(D\) are in A and (ii) \(w(P) \leq (w(C_{from}) + w(D)) / i\). We cover the two cases where a special merge can happen.

The first case is during the combining step. Using the algorithm notation, let \(C_1 = C_{to}\) be the first component considered and \(l_{C_1}\) be the compressed distance to its nearest compatible component at the time of the special merge. We have \(\text{rank}(C_1) = i\), and \(C_{from} = C_3\) satisfies \(D(C_1, C_3) < l_{C_1} / (rank(C_1) + 2)\) and \(t_{max}(C_3) \geq t_{max}(C_1) + l_{C_1}\). Because \(D\) and \(C_3\) are not compatible with \(C_1\), this means that their rank is strictly less than \(\text{rank}(C_1) = i\), which is the rank used for the special merge. Using 2, this implies that \(C_3\) and \(D\) are made from edges in \(\mathcal{F}_{i-1}\), so in \(A\) because \(\mathcal{F}_{i-1} \subseteq \mathcal{F'}_{i-1}\).

We have \(t_{max}(C_3) \geq t_{max}(C_1) + l_{C_1}\), so there exists a request \(v \in V(C_3)\) such that \(t(v) \geq t_{max}(C_1) + l_{C_1}\). We have \(w(P) = D(C_1, C_3) < l_{C_1} / (\text{rank}(C_1) + 2)\). Given \(P\), a simple path on the components, we now describe how to get \(P'\), a simple path on the requests. To do so, we consider the fact that each edge in \(P\) starts and ends at a specific request within its incident component. To link these together, consider two consecutive edges in \(P\): the request where the first edge ends and the request where the second edge begins belong to a same component \(C\). We can therefore connect these two requests using the simple path between them in the spanning tree \(T(C)\). We end up with a path \(P'\) from some \(u \in C_1\) to \(v\) made of two disjoint sets of edges: the first \(E_1\) consists of the edges between requests in different components. We note that \(w(E_1) = w(P)\). The second \(E_2\) consists of edges between requests in the same component. By construction, these edges belong to \(T(C_3)\) or to the spanning tree of components in \(D\). Moreover, each edge in the spanning tree of a component is only used at most once: \(P\) is a shortest path and does not pass through a component twice. Therefore \(w(E_2) \leq w(C_3) + w(D)\). Because \(d\) satisfies the triangle inequality and \(P'\) is a path from \(u\) to \(v\), we get: \[\begin{align} w(P') &\geq d(u,v) \\ & \geq |t(v) - t(u)| \\ & \geq t(v) - t(u) \\ & \geq t_{max}(C_1) + l_{C_1} - t_{max}(C_1) \\ & \geq l_{C_1} \\ & \geq w(P) \cdot (\text{rank}(C_1) + 2) \\ & = w(P) \cdot (i+2) \end{align}\] We also have: \[\begin{align} w(P') &= w(E_1) + w(E_2) \\ & \leq w(P) + (w(C_3) + w(D)) \end{align}\] From these two inequalities, we get the desired property \(w(P) \leq (w(C_3) + w(D)) / (i+1) \leq (w(C_3) + w(D)) / i = (w(C_{from}) + w(D)) / i\).

The second case is in the nearby fixup procedure, using the algorithm notation, when merging a component \(C_1 = C_{from}\) to its closest component \(C_2 = C_{to}\) having a rank of at least \(\text{nrank}(C_1)\), or nearby rank of at least \(\text{nrank}(C_1) + 1\). We remark that \(i = \text{nrank}(C_1)\) and that this special merge can happen in the middle of an iteration, meaning some invariants may not hold. Because components in \(D\) are closer to \(C_1\) than \(C_2\), it implies that their rank is strictly less than \(\text{nrank}(C_1) = i\). Given that components in \(D\) were not touched by the algorithm in the current iteration so far, we can use 2, which implies that they are made from edges in \(\mathcal{F}_{i-1}\), so in \(A\) because \(\mathcal{F}_{i-1} \subseteq \mathcal{F'}_{i-1}\). We now consider \(C_1\). The fixup procedure might have already performed some special merge before this one. However, we remark that the nearby rank of \(C_1\) increases by at least \(1\) during each fixup iteration. Therefore, each special merge in previous iterations of the fixup procedure contributed to \(S'_k\) for some \(k < i\), which is in \(A\). Moreover, the regular merge right before the call to the fixup procedure had rank at most \(\text{nrank}(C_1) = i\), so the edges added were part of \(R_k\) for some \(k \leq i\), which is also in \(A\). Finally, for the remaining edges, which were already present before the beginning of the algorithm iteration, we can use our invariants from 3 2: given that \(\text{rank}(C_1) < \text{nrank}(C_1) = i\), all remaining edges are part of \(\mathcal{F}_{i-1}\).

We consider the time \(t'\) at which \(C_1\) got assigned \(i\) as its nearby rank. At time \(t'\), \(C_1\) was possibly smaller and as such, we call \(C_1'\) the component \(C_1\) as it was at time \(t'\), we have \(C'_1 \subseteq C_1\). Getting a non-\(\bot\) nearby rank can only happen during a regular merge of some component \(C'_{from}\) into a component \(C'_{to}\) at rank \(i\). Let \(l\) be the distance from \(C'_{from}\) to \(C'_{to}\) at this time, \(l = D_{t'}(C'_{from}, C'_{to})\). Because \(C'_1\) was given a nearby rank, it means that \(D_{t'}(C'_{from}, C'_1) < l / (i + 1)\).

We want to prove that while \(C'_1\) has not been merged, there is always a component of rank at least \(\text{nrank}(C_1)\) with distance at most \(l / (i + 1)\) from \(C'_1\). This, in particular, implies that \(D(C_1,C_2) \leq l / (i + 1)\). Using 2, we consider the shortest path \(P\) from \(C'_1\) to \(C'_{from}\) at time \(t'\). We remark that it only passes through components with distance less than \(l / (i + 1)\) from \(C'_{from}\), hence all of these components’ nearby rank was set to at least \(i\). We observe using 7 that after \(t'\), these components along the path are either the same or merged into a component of rank at least \(i\). Moreover, after \(t'\), \(C'_{from}\) has itself merged into a component of rank at least \(\text{nrank}(C_1)\). Therefore, going along \(P\) after \(t'\), we always find a component of rank at least \(i\) after some even components. By definition of \(C_2\), we get that \(D(C_1, C_2) \leq w(P) < l /(i+1)\).

We now want to give a lower bound on \(w(C_1)\). To be more precise, we want to prove that \(w(C_1) \geq l \cdot(1 - 1/(i+1))\). We remark that in the nearby fixup procedure, \(C_1\) is odd. Hence, using \(\ref{lemma:request-in-odd}\), there exists a request \(v \in V(C_1)\) which was always part of an odd component until \(t\). We consider the state of this request at time \(t'\):

• Request \(v\) already arrived by \(t'\) (\(t(v) < t'\)). But then, the component \(v\) was in at time \(t'\) was an odd component \(C_v\) and as a consequence was compatible with \(C'_{from}\). \(C'_{to}\) being the closest compatible component at this time, this means that \(D_{t'}(C'_{from}, C_v) \geq D_{t'}(C'_{from}, C_{to}) = l\). Because \(C'_1\) was an even component at time \(t'\), we get that: \[\begin{align} D_{t'}(C'_1, C_v) &\geq D_{t'}(C'_{from}, C_v) - D_{t'}(C'_{from}, C'_1) \\ &\geq l - l/(i+1) = l \cdot(1 - 1/(i+1)) \end{align}\] Let \(u \in C'_1\), using 2, we have therefore \(d(u,v) \geq D(C'_1, C_v) \geq l \cdot(1 - 1/(i+1))\). We remark that we chose \(v\) such that it was in \(V(C_1)\). As a consequence, both \(u\) and \(v\) are in \(V(C_1)\). Because \(d\) satisfies the triangle inequality, the spanning tree \(T(C_1)\) on \(V(C_1)\) satisfies \(w(T(C_1)) \geq d(u,v) \geq l \cdot(1 - 1/(i+1))\).

• Request \(v\) arrived after \(t'\) (\(t(v) \geq t'\)). We note that by design of the algorithm, \(t' \geq t_{max}(C'_{from}) + 2D_{t'}(C'_{from}, C_{to}) = t_{max}(C'_{from}) + 2l\). Moreover, using 2, \(\text{rank}(C'_{from}) < i\), so \(C_1'\) satisfies \(D_{t'}(C'_{from}, C'_1) < l / (i + 1) \leq l / (\text{rank}(C'_{from}) + 2)\). As a consequence, the algorithm ensured in the combining step that \(t_{max}(C'_1) \leq t_{max}(C'_{from}) + l\). Let \(u \in C_1'\), we therefore have: \[\begin{align} d(u,v) &\geq |t(v) - t(u)| \\ & \geq t(v) - t(u) \\ & \geq t_{max}(C'_{from}) + 2l - (t_{max}(C'_{from}) + l) \\ & = l \end{align}\] We remark that both \(u\) and \(v\) are requests in \(C_1\) and use the same argument as before: because \(d\) satisfies the triangle inequality, the spanning tree \(T(C_1)\) verifies: \[\begin{align} w(C_1) \geq d(u,v) \geq l > l \cdot(1 - 1/(i+1)) \end{align}\]

From the previous points, we get that: \[\begin{align} W(P) &= D(C_1, C_2) \\ &\leq 1 /(i+1) \cdot l \\ & \leq 1/(i+1) \cdot (1 - 1/(i+1))^{-1} \cdot w(C_1) \\ & = w(C_1) / i \\ &\leq (w(C_{from}) + w(D)) / i \end{align}\]

We showed that (i) the edges of \(T(C_{from})\) and the spanning trees of components in \(D\) are in A and (ii) \(w(P) \leq (w(C_{from}) + w(D)) / i\). We remark that the resulting component has at least an edge in \(S'_i\) and therefore, because of (i), cannot be used again as \(C_{from}\) or in \(D\) for a new special merge contributing to \(S'_i\). Hence, each edge in \(A\) is used at most once as \(C_{from}\) or \(D\) for a merge contributing to \(S'_i\). Moreover, using (i), these components are made only using edges from \(A\). Thus, using (ii), summing over all merges which contribute to \(S'_i\), we get \(w(S'_i) \leq w(A) / i = \left(w(\mathcal{F}'_{i-1}) + w(R_i) \right) / i\). ◻

Proof. We consider \(H_k = \sum_{i=1}^k 1/k\) the harmonic series. We prove by induction for \(i \in [\![0, \lfloor \log m\rfloor ]\!]\) that: \[\begin{align} w(\mathcal{F}'_i) \leq 2 \cdot (i+1) \cdot (i + H_i)\cdot OPT \end{align}\]

Initialization: For \(i = 0\), \(\mathcal{F}'_0\) contains no edge, so \(w(\mathcal{F}'_0) = 0\). We remark that the right term is also \(0\), so the property holds.

Induction: Let \(i \in [\![1, \lfloor \log m\rfloor ]\!]\), we assume that the property is true for \(w(\mathcal{F}'_{i-1})\). We remark that \(\mathcal{F}'_{i} = R_i \cup S'_i \cup {F}'_{i-1}\). Using 11 10, we get that \(w(R_i) \leq 2i \cdot OPT\) and \(w(S'_i) \leq \left(w(R_i) + w(\mathcal{F}'_{i-1})\right)/ i\). Therefore, using the induction hypothesis: \[\begin{align} w(\mathcal{F}'_{i}) &\leq w(R_i) + w(S'_i) + w(\mathcal{F}'_{i-1}) \\ & \leq (1 + 1/i) \cdot w(R_i) + (1 + 1/i) \cdot w(\mathcal{F}'_{i-1})\\ & \leq 2 \cdot (1+1/i) \cdot (i+1) \cdot OPT + 2 \cdot (1+1/i) \cdot i \cdot (i - 1 + H_{i-1}) \cdot OPT \\ & = 2 \cdot (i+1) \cdot (1+1/i) \cdot OPT + 2 \cdot (i+1) \cdot (i - 1 + H_{i-1}) \cdot OPT \\ & = 2 \cdot (i+1) \cdot (1 + 1/i + i - 1 + H_{i-1}) \cdot OPT \\ & = 2 \cdot (i+1) \cdot (i + H_i)\cdot OPT \end{align}\]

Conclusion: We have: \[\begin{align} w(\mathcal{F}) = w(\mathcal{F}'_{\lfloor \log m\rfloor}) \leq 2 \cdot (\lfloor \log m\rfloor+1) \cdot (\lfloor \log m\rfloor + H_{\lfloor \log m\rfloor})\cdot OPT \end{align}\]

Using the property of the harmonic series \(H_k = \Theta(\log k) = o(k)\), we get \(w(\mathcal{F}) \leq OPT \cdot (2 + o(1)) \log^2m\). ◻

Proof. As soon as a component has two or more requests not in a greedy instance, it makes them join its own greedy instance two at a time. From this, we conclude that at any given time, even components have no requests not inside a greedy instance while odd components have exactly one. The lemma follows from this observation. ◻

Proof. At any time \(t\), in the algorithm we consider \(\mathcal{W}(t)\) the oriented graph whose vertices are the odd components \(\mathscr{C}_{odd}(t)\) and edges are the waiting edges. We call \(\mathcal{W}(t)\) the waiting forest. Because a waiting edge goes from one component to another with strictly lower rank, it cannot have cycles. Moreover, each odd component waits on at most a single component, so has out-degree at most \(1\) in \(\mathcal{W}(t)\). From these observations, we conclude that \(\mathcal{W}(t)\) is indeed a forest. Moreover, each oriented tree \(T\) in \(\mathcal{W}(t)\) has its edges oriented towards the root, which has out-degree \(0\).

We also remark that a component is active if and only if its out-degree in \(\mathcal{W}(t)\) is \(0\). Therefore, all trees in \(\mathcal{W}(t)\) consist of a single active component being its root, and some waiting components.

We claim that each tree in \(\mathcal{W}(t)\) has size at most \(\lfloor \log m \rfloor + 1\). The reason is that, using 1, the maximum component rank is \(\lfloor \log m \rfloor\). So if a tree has a greater size, using the pigeonhole principle, we could find two components in this tree with the same rank, but the tree pruning procedure would immediately merge them together. Thus, we have:

• A graph where each active and waiting components appear as vertices.

• Each connected component of this graph contains exactly one active component.

• Each connected component of this graph has size at most \(\lfloor \log m \rfloor + 1\)

Using these properties together, we get that \(|\mathscr{C}_w(t)| \leq \lfloor \log m \rfloor \cdot |\mathscr{C}_a(t)| \leq \log m \cdot |\mathscr{C}_a(t)|\) ◻

Proof. We now want to bound the time an odd component stays active. Let \(r \in [\![0, \lfloor \log m\rfloor ]\!]\), we consider a component \(C(t)\) of rank \(r\) evolving from the time \(t_{re}(C, r)\) where it reached rank \(r\) to the time \(t_{le}(C, r)\) where either: it merges into a bigger component, its rank increased, or the time the algorithm ends if this component is even and never gets used again. Using 9, we can find \(C' \in \mathfrak{D}_r\) such that \(C(t_{le}(C,r)) = C'\).

We will divide the time \(C(t)\) stays active in two and give an upper bound for each of these intervals. We say that \(C(t)\) stabilizes at rank \(r\) if no more odd component merges into \(C(t)\) while its rank is \(r\). We denote by \(t_{st}(C, r)\) the stabilization time of \(C(t)\) at rank \(r\). We have \(t_{re}(C,r) \leq t_{st}(C,r) \leq t_{le}(C,r)\). We will give an upper bound on the amount of time a component can stay active before its stabilization time and after it at a given rank.

Assume \(r \geq 1\), \(C'\) is a component in \(\mathfrak{D}_r\) where components are defined as connected components in the forest \(\mathcal{F}_r\). Because \(\mathcal{F}_{r-1} \subseteq \mathcal{F}_r\), we can find a set of components \(B \subseteq \mathfrak{D}_{r-1}\) such that \(V(C') = \cup_{C" \in B} V(C")\), i.e \(C'\) is made from components of \(B\) merging together. Using 9, we can show that every component \(C"\) in \(B\) existed at some time \(t'\), different for each component, right before it merged into \(C(t')\). Let \(C_1, ..., C_k\) be the odd components of \(B\). Using 6, we can find some requests \(v_1 \in C_1, ..., v_k \in C_k\) such that each of those requests was in an odd component until it got merged into \(C\). We will show that \(C\) can remain active at most \(3w(C')\) units of time between \(t_{re}(C,r)\) and \(t_{st}(C,r)\).

Let \(t_1 = t_{re}(C,r)\) and \(t_2 = t_{st}(C,r)\). We consider \(u = repr(C(t_1))\) which by design stays the same at any time and is already part of \(C(t_1)\). We consider: \[\begin{align} l = \max_{i \in [\![1, k ]\!]} d(u, v_i) \end{align}\] We claim that after \(t_1 + w(C') + 2l\) and before \(t_2\), \(C(t)\) cannot be active. To do so, consider some time \(t\) such that \(t > t_1 + w(C') + 2l\) and \(t < t_2\), let us show that \(C(t)\) is even or waiting. If \(C(t)\) is even, we are done, so let us assume that \(C(t)\) is odd. Let \(l'\) be the distance from \(C(t)\) to its closest compatible component, we claim that \(l' \leq l\). The reason is that because \(t < t_2\), the component did not stabilize yet, so there must exist some \(C_i\) such that \(C_i\) did not merge into \(C(t)\) yet. Therefore, by definition, at time \(t\), \(v_i\) is in an odd component \(\tilde{C}\) distinct from \(C(t)\). Because this component is odd, it is compatible with \(C(t)\) and using 2, \(D_t(C(t), \tilde{C}) \leq d(u, v_i) \leq l\), so by minimality \(l' \leq l\). Moreover, there must exist some \(u' \in V(C(t))\) such that \(t_{max}(C(t)) = t(u')\). Because \(u\) and \(u'\) are both in \(C'\) and \(d\) satisfies the triangle inequality, we have: \[\begin{align} t_{max}(C(t)) - t(u) &= t(u') - t(u) \\ & \leq d(u', u) \\ & \leq w(C') \end{align}\] Because \(u = repr(C(t_1))\), we have \(t(u) \leq t_1\), so \(w(C') \geq t_{max}(C(t)) - t_1\). Combining these inequalities, we get: \[\begin{align} t &> t_1 + w(C') + 2l \\ &\geq t_1 + t_{max}(C(t)) - t_1 + 2l' \\ &\geq t_{max}(C(t)) + 2l' \end{align}\] Because \(t\) is after \(t_{max}(C(t)) + 2l'\), where \(l'\) is the distance from \(C(t)\) to its closest compatible component, and no merge happened yet, it means that \(C(t)\) is waiting. Moreover, we note that \(l\) is the distance between \(u\) and some \(v_i\) and both \(u\) and \(v_i\) are in \(V(C')\). Because \(d\) satisfies the triangle inequality and \(T(C')\) is a spanning tree over \(V(C')\), we get that \(l \leq w(C')\). Therefore, between \(t_1\) and \(t_2\), \(C(t)\) can only be active until time \(\min(t_2, t_1 + 3w(C'))\) and thus can remain active at most \(3w(C')\) units of time. We remark that components with \(r = 0\) are singletons and therefore, \(t_2 = t_1\) hence this property holds immediately in this case.

We now consider the time \(C\) spends active between \(t_{st}(C,r)\) and \(t_{le}(C,r)\). Let \(t_1 = t_{st}(C,r)\) and \(t_2 = t_{le}(C,r)\). By our choice of \(t_1\), being the stabilization time, only even component will merge with \(C\) in this time frame, so \(C\) will keep the same parity, and in particular the same one as \(C(t_2) = C'\). If \(C'\) is even, \(C\) will remain even, so not active between \(t_1\) and \(t_2\). We now assume that \(C'\) is odd.

Because all final components are even, it follows that at time \(t_2\), \(C(t_2)\) will merge into a bigger component or its rank will increase, so we can focus on this case only. However, it turns out that bounding the time between \(t_1\) and \(t_2\) for a single component cannot be done efficiently. Instead, we will do so by considering a component and bounding together the time spent active after stabilization of all lower rank components which merge into it.

We thus consider a new \(r > 0\) and \(C \in \mathfrak{D}_r\). As explained above, we will take a new approach and instead bound the active time after stabilization of all odd components which merge into \(C\). Because \(\mathcal{F}_{i-1} \subseteq \mathcal{F}_{i}\), we can consider the sub-components of \(C\) in \(\mathfrak{D}_{r-1}\). Let \(C'_1, ..., C'_k\) be the set of all odd such sub-components. Using 6, for each \(C'_i\), we can find a request \(v_i\) such that \(v_i\) was always part of an odd component until it merged into \(C\). We observe at any time before merging into \(C\), the component containing \(v_i\) was odd and thus compatible with any other component.

We note that \(v_1, .., v_k\) are requests in the spanning tree \(T(C)\), we consider an Euler tour \(E_T\) from \(T(C)\) where we only keep the vertices in \(\{v_1, ..., v_k\}\). Because we are in a metric space, \(w(E_T) \leq 2w(T(C)) = 2w(C)\). We orient the tour \(E_T\) in an arbitrary way and for each \(v_i\), we consider \(l_i\) to be the distance from \(v_i\) to its right neighbor along \(E_T\). By construction, \(\sum_{i=1}^k l_i = w(E_T) \leq 2w(C)\).

We now consider an odd component \(C'_i\) among these sub-components. Let \(C_i(t)\) be the component representing it during the algorithm execution. Let \(t_1 = t_{st}(C_i, \text{rank}(C'_i))\) and \(t_2 = t_{le}(C_i, \text{rank}(C'_i))\). We want to give an upper bound on the time \(C_i(t)\) stays active after stabilization and until it merges into \(C\). Because no odd component joins \(C_i\) after \(t_1\) and \(v_i\) is always part of an odd component until it joins \(C_i\), we conclude that \(v_i\) joined \(C'_i\) before \(t_1\), and \(t(v_i) \leq t_1\). With the same argument as before, we get that for all \(t \geq t_1, \;t_{max}(C_i(t)) \leq t(v_i) + w(C'_i) \leq t_1 + w(C'_i)\). We claim that between \(t_1 + w(C'_i) + 2l_i\) and \(t_2\), component \(C_i(t)\) will always be waiting. We consider some time \(t\) such that \(t > t_1 + w(C'_i) + 2l_i\) and \(t < t_2\). Because \(t\) is after the stabilization time \(t_1\), the parity of \(C'_i\) does not change so \(C_i(t)\) is odd. We note that by definition, \(l_i\) is the distance between \(v_i \in C_i(t)\) and some \(v_j\) in another component which is compatible with \(C_i(t)\). Therefore, using 2, the compressed distance between \(C_i(t)\) and its closest compatible component \(l'\) is at most \(l_i\). We remark that \(t > t_1 + w(C'_i) + 2l_i \geq t_{max}(C_i(t)) + 2l'\), therefore if the component was not waiting, it would have already merged into its closest component, so it is waiting. Thus after \(t_1\), component \(C_i(t)\) is active at most \(w(C'_i) + 2 l_i\) units of time.

We now compute the total active time after stabilization of odd components in \(B\). Using the previous part, it is at most: \[\begin{align} \sum_{i = 1}^k (w(C'_i) + 2l_i) \end{align}\] We remark that \(\sum_{i=1}^k l_i \leq 2w(C)\) and all \(T(C'_i)\) are disjoint and a subset of \(T(C)\), so \(\sum_{i=1}^k w(C'_i) \leq w(C)\). Therefore, the total active time for components which merge into \(C\) after stabilization is at most \(5w(C)\).

We can finally compute the total active time for all components, which is the sum of the active time before stabilization and after stabilization for each component at each rank. We also note that \(w(C) = 0\) for a component of rank \(0\), as they are singletons: \[\begin{align} \int_{t \geq 0} |\mathscr{C}_{a}(t)|dt &\leq \sum_{r = 0}^{\lfloor \log m \rfloor} \sum_{C \in \mathfrak{D}_r} 3w(C) + \sum_{r = 1}^{\lfloor \log m \rfloor} \sum_{C \in \mathfrak{D}_r} 5w(C) \\ & = 8 \sum_{r = 1}^{\lfloor \log m \rfloor} \sum_{C \in \mathfrak{D}_r} w(C) \\ & = 8 \sum_{r = 1}^{\lfloor \log m \rfloor} w(\mathcal{F}_r) \\ & \leq 8 \sum_{r = 1}^{\lfloor \log m \rfloor} w(\mathcal{F}) \\ & \leq 8 \cdot \log m \cdot w(\mathcal{F}) \end{align}\] ◻

Proof. We use the fact that at any time, \(\mathscr{C}_{odd}(t) = \mathscr{C}_w(t) \cup \mathscr{C}_a(t)\). Therefore, \(|\mathscr{C}_{odd}(t)| \leq |\mathscr{C}_w(t)| + |\mathscr{C}_a(t)|\). We have: \[\begin{align} \Delta_c &= \int_{t \geq 0} |\mathscr{C}_{odd}(t)|dt && \text{from \ref{lemma:bound-delta-odd}} \\ & \leq \int_{t \geq 0} |\mathscr{C}_{odd}(t)|dt \\ & \leq \int_{t \geq 0} (|\mathscr{C}_w(t)| + |\mathscr{C}_a(t)|)dt \\ & \leq \int_{t \geq 0} (\log m |\mathscr{C}_a(t)| + |\mathscr{C}_a(t)|)dt && \text{from \ref{lemma:compare-active-waiting}}\\ & \leq (1 + o(1)) \log m \int_{t \geq 0} |\mathscr{C}_a(t)|dt \\ & \leq (1 + o(1)) \log m \cdot 8 \cdot \log m \cdot w(\mathcal{F}) && \text{from \ref{lemma:bound-active-forest}} \\ &\leq (8 + o(1)) \log^2 m \cdot w(\mathcal{F}) \\ &\leq (16 + o(1)) \log^4 m \cdot OPT && \text{from \ref{theorem:bound-forest-weight}} \end{align}\] ◻

Proof. We define \(\mathfrak{D}= \bigcup_{r=0}^{\lfloor \log m \rfloor} \mathfrak{D}_r\) the multiset of all possible components in our component decompositions. We consider the greedy invocation associated with a request \(u \in V_{req}\), we remark that as long as the component containing \(u\) does not merge into another component, its greedy invocation can receive requests from within the component. Let \(C\) be the component with representative \(u\) right before it got merged into another component or at the end of the algorithm if this never happens. Using 9, we note that \(C\) corresponds to a component in \(\mathfrak{D}_r\) for some \(r \geq 0\). Moreover, a component having a single representative, this component in \(\mathfrak{D}_r\) cannot correspond to another component with a different representative. Therefore, for each request \(u \in V_{req}\), we can find a distinct component \(C\) in \(\mathfrak{D}\) such that the greedy instance on \(u\) only matches requests in \(V(C)\). For a component \(C \in \mathfrak{D}\), we denote by \(\text{req}(C)\) the set of requests that are processed by the greedy instance associated with \(C\). If no request got attached to the greedy instance on \(C\), then \(\text{req}(C) = \emptyset\). We remark that for all \(C \in \mathfrak{D}\), \(\text{req}(C) \subseteq V(C)\).

We consider a component \(C \in \mathfrak{D}\) and want to bound the cost of the greedy associated with this component. We note that, by design of the algorithm, requests join the greedy algorithm with a different arrival time compared to their original arrival time. In particular, the arrival time of a request in the greedy invocation is \(t_j(u)\) instead of \(t_a(u)\). \(T(C)\) being a spanning tree over \(V(C)\), we can consider an Euler tour \(E_C\) from the spanning tree \(T(C)\) where we then remove requests which are not in \(\text{req}(C)\). Therefore, \(E_C\) is a tour on \(\text{req}(C)\). Because we are in a metric space, \(w(E_C) \leq 2w(C)\). We now consider \(w'\) and \(d'\) to be the modified edge weight and distance taking into account the time of joining the greedy algorithm \(t_j(u)\) instead of the time of arrival \(t_a(u)\) for a request \(u\). We observe that by design of our algorithm, each greedy instance uses \(d'\) instead of \(d\) for the distance. For an edge \(e = (u,v)\), we have: \[\begin{align} w'(e) &= d'(u,v) \\ & = d((x(u), t_j(u)), (x(v), t_j(v))) \\ & \leq d((x(u), t_j(u)), (x(u), t_a(u))) + d((x(u), t_a(u)), (x(v), t_a(v))) + d((x(v), t_a(v)), (x(v), t_j(v))) \\ & = t_j(u) - t_a(u) + d(u,v) + t_j(v) - t_a(v) \\ & = \delta_c(u) + \delta_c(v) + d(u,v) \end{align}\] We note that \(E_C\) is a tour of \(\text{req}(C)\), so each request in \(\text{req}(C)\) appears as the endpoint of exactly two edges in \(E_C\), therefore: \[\begin{align} w'(E_C) \leq w(E_C) + 2\sum_{v \in \text{req}(C)} \delta_c(v) \leq 2 w(C) + 2\sum_{v \in \text{req}(C)} \delta_c(v) \end{align}\] Moreover, \(E_C\) is a valid traveling salesman tour for \(\text{req}(C)\), therefore the optimal traveling salesman tour for requests handled by the greedy invocation on \(C\) has weight at most \(2 w(C) + 2\sum_{v \in \text{req}(C)} \delta_c(v)\). We denote by \(M_C\) and \(W_C\) the communication cost and matching cost of the greedy instance in \(C\) respectively, we can now apply [theorem:greedy-upper-bound]: \[\begin{align} W_C + M_C &\leq \frac{5}{2}(\lceil \log |\text{req}(C)| \rceil + 1) \left( 2 w(C) + 2\sum_{v \in req(C)} \delta_c(v) \right) \\ & \leq 5 (\lceil \log m \rceil + 1) \left( w(C) + \sum_{v \in req(C)} \delta_c(v) \right) \end{align}\]

We note that each request appears only in the greedy instance of exactly a single component, therefore \(\displaystyle \sum_{C \in \mathfrak{D}} \sum_{v \in \text{req}(C)}\delta_c(v) = \sum_{v \in V_{req}} \delta_c(v)\). We can now bound the total wait time and communication cost, given that each request is matched in a single greedy instance:

\[\begin{align} \Delta_g + M_g &= \sum_{C \in \mathfrak{D}} \left( W_C + M_C \right) \\ & \leq \sum_{C \in \mathfrak{D}} \left( 5 (\lceil \log m \rceil + 1) \left( w(C) + \sum_{v \in \text{req}(C)} \delta_c(v) \right) \right) \\ & = (5 + o(1)) \log m \left( \sum_{C \in \mathfrak{D}} w(C) + \sum_{C \in \mathfrak{D}} \sum_{v \in \text{req}(C)}\delta_c(v) \right) \\ & = (5 + o(1)) \log m \left( \sum_{r = 1}^{\lfloor \log m \rfloor} \sum_{C \in \mathfrak{D}_r} w(C) + \sum_{v \in V_{req}} \delta_c(v) \right) \\ & = (5 + o(1)) \log m \left( \sum_{r = 1}^{\lfloor \log m \rfloor} w(\mathcal{F}_r) + \Delta_c \right) \\ & \leq (5 + o(1)) \log m \left( \sum_{r = 1}^{\lfloor \log m \rfloor} w(\mathcal{F}) + \Delta_c \right) \\ & \leq (5 + o(1)) \log m \cdot \left( \log m \cdot w(\mathcal{F}) + \Delta_c \right) \\ & \leq (5 + o(1)) \log m \cdot ( (2 + o(1)) \log^3 m \cdot OPT \\ & \;\;\;\;\;\;\;\;+ (16 + o(1)) \log^4 m \cdot OPT ) && \text{Using \ref{theorem:bound-forest-weight} \ref{theorem:bound-waiting-outside}} \\ & = (80 + o(1)) \log^5 m \cdot OPT \end{align}\] ◻

Proof. The total cost of the algorithm is: \[\begin{align} \Delta_c + \Delta_g + M_g &\leq (16 + o(1)) \log^4 m \cdot OPT + (80 + o(1)) \log^5 m \cdot OPT && \text{Using \ref{theorem:bound-waiting-outside} \ref{theorem:bound-waiting-inside}} \\ & = (80 + o(1)) \log^5 m \cdot OPT \end{align}\] Because \(OPT\) is the optimal cost an algorithm knowing in advance the arrival of every request achieves, ONLINE_MATCHING has indeed competitiveness \((80 + o(1)) \log^5 m\). ◻

Proof. We consider a solution \((p_i, q_i, t_i)_{i \in [\![1;m/2]\!]}\) to the MPMD problem, for \(i \leq m/2\), we observe that \(t_i \geq \max(t(p_i), t(q_i))\), as a consequence: \[\begin{align} |t_i - t(p_i)| + |t_i - t(q_i)| &\geq |\max(t(p_i), t(q_i)) - t(p_i)| + |\max(t(p_i), t(q_i)) - t(q_i)| \\ & = |t(p_i) - t(q_i)| \end{align}\] Therefore: \[\begin{align} g(x(p_i), x(q_i)) + |t_i - t(p_i)| + |t_i - t(q_i)| \geq g(x(p_i), x(q_i)) + |t(p_i) - t(q_i)| = d(p_i, q_i) \end{align}\]

As a consequence: \[\begin{align} \sum_{i=1}^{m/2} g(x(p_i), x(q_i)) + |t_i - t(p_i)| + |t_i - t(q_i)| \geq \sum_{i=1}^{m/2} d(p_i, q_i) \end{align}\] Conversely, if we consider a solution \((p_i, q_i)_{i \in [\![1;m/2]\!]}\) to the offline problem, we define \(\forall i \leq m/2\), \(t_i = \max(t(p_i), t(q_i))\). We observe that with this definition, \(|t_i - t(p_i)| + |t_i - t(q_i)| = |t(p_i) - t(q_i)|\), thus: \[\begin{align} \sum_{i=1}^{m/2} d(p_i, q_i) = \sum_{i=1}^{m/2} g(x(p_i), x(q_i)) + |t_i - t(p_i)| + |t_i - t(q_i)| \end{align}\] From the first result, any online solution of cost \(C\) yields an offline solution of cost at most \(C\). From the second result, any offline solution of cost \(C'\) yields an online solution of cost \(C'\). Using these two properties together, we conclude that \(OPT = OPT'\). ◻

Proof. Let \(M_{OPT}\) be the min-cost perfect matching of weight \(W_{OPT}\). Let \(E \subseteq M_{OPT}\) be the subset of these edges such that the two endpoints of any edge are in different components. By identifying a vertex to the component containing it, we can define \(G' = (\mathscr{C}, E)\) as an undirected graph on components. We note that this graph is not simple (there may be multiple edges between two components), but it has no self-loops. We consider a component \(C \in \mathscr{C}\), let \(k\) be the number of internal edges (edges with both endpoints in \(V(C)\)) in \(M_{OPT}\). Because every vertex is the endpoint of exactly one edge of \(M_{OPT}\), we get that \(\mathrm{deg}_{G'}(C) = |V(C)| - 2k\). In particular, the parity of \(\mathrm{deg}_{G'}(C)\) is the same as the parity of \(|V(C)|\). Therefore, a component in \(G'\) has odd degree if and only if it is an odd component.

Let \(k_{odd}\) be the number of odd components in \(\mathscr{C}\), which is also the number of vertices with odd degree in \(G'\). Using the handshaking lemma, \(k_{odd}\) is even. We claim that we can find a set of \(k_{odd}/2\) edge-disjoint paths \((P_i)_{i \in [\![1,k_{odd}/2]\!]}\) such that each path is between two distinct odd vertices in \(G'\) and every odd vertex in \(G'\) appears exactly once as the endpoint of one of those path.

To do so, we first prove that we can always find a path between two distinct vertices with odd degree in \(G'\). If we consider \(v_1\) a vertex with odd degree, it must have degree at least \(1\) so we can find an edge \(e_1 = (v_1, v_2)\). If \(v_2\) has odd degree, then \(e_1\) satisfies the property we look for as a path. Otherwise, we remove \(e_1\) from \(G'\), the degree of \(v_1\) then becomes even while the degree of \(v_2\) becomes odd. We can repeat this operation now starting with \(v_2\) until we end up on a vertex with odd degree, this gives us the path we are looking for.

When we have such a path, we remove it from \(G'\): the degree of its two endpoints becomes even and the degree of other vertices does not change. We can repeat this process \(k_{odd}/2\) times and will be left with only vertices with even degree. From this, we get the set of edge-disjoint paths \((P_i)_{i \in [\![1,k_{odd}/2]\!]}\) described above.

We consider one such path \(P = C_1 \rightarrow C_2 \rightarrow \ldots \rightarrow C_l\), let \(w(P)\) be the sum of the edges along such a path. According to our assumptions, \(C_1\) and \(C_l\) are distinct components. Let \(s_1 < l\) be the last index \(C_1\) appears along path \(P\) and let \(s_2 \in ]\!]s_1, l]\!]\) be the index after \(s_1\) where an odd component distinct from \(C_1\) appears. We remark that \(C_{s_1} \rightarrow C_{s_1 + 1} \rightarrow \ldots \rightarrow C_{s_2}\) is a path between two distinct odd components where parts within even components are ignored. Thus by definition, the weight of this path is at least \(D(C_1, C_{s_2})\). Therefore, \(w(P) \geq D(C_1, C_{s_2}) \geq r_{C_1}\). By symmetry, \(w(P) \geq r_{C_2}\).

We remark that the paths \((P_i)_{i \in [\![1,k_{odd}/2]\!]}\) are edge-disjoint, therefore: \[\begin{align} \sum_i w(P_i) &= w\left(\bigcup_i P_i \right) \\ & \leq w(M_{OPT}) \\ & = W_{OPT} \end{align}\] Moreover, each odd component appears exactly once at the endpoint of a path in \((P_i)_i\) and each path has exactly two endpoints, therefore: \[\begin{align} \sum_i 2 w(P_i) \geq \sum_{C \in \mathscr{C}_{odd}} r_C \end{align}\] Putting the two previous equations together, we get our result: \[\begin{align} \sum_{C \in \mathscr{C}_{odd}} r_C \leq 2 W_{OPT} \end{align}\] ◻

Proof. Let \(M\) be the matching output by \(M_{GREEDY}\). We first want to bound the space cost \(w(M)\) of the matching. We will use 3 again. For \(u \in V_{req}\) a request, let \(v\) be the request GREEDY_ONLINE matches it to. We define \(l_u = d(u,v) / 2\). We show that it satisfies the properties required by the lemma:

• Let \(p,q\) be two distinct requests. If the greedy algorithm matched \(p\) with \(q\), then \(l_p = l_q\) and \(d(p,q) = 2 l_p \geq \min (l_p, l_q)\). Otherwise, without loss of generality, let us assume that \(p\) got matched before \(q\). We now consider the algorithm at the time it matched \(p\) with some other vertex, there are two cases:

  • \(p\) was the first request considered (\(u\) in the context of the algorithm). Let \(v\) be the vertex matched to it. The algorithm waited past time \(t(p) + d(p,v)\) to match it, which using 1 implies that all requests within a radius \(d(p,v)\) from \(p\) already arrived. Because it decided to match \(p\) with \(v\) and not \(q\) which was unmatched, it means that \(q\) had not arrived yet or was further away from \(u\) than \(v\). In both cases, \(d(p,q) \geq d(p,v)\), so \(2l_p = d(p,v) \leq d(p,q)\). Hence \(d(p,q) \geq 2l_p \geq \min (l_p, l_q)\).

  • \(p\) was the second request considered (\(v\) in the context of the algorithm). The algorithm therefore matched \(p\) to some other request \(u\) at time \(t\). We have \(t \geq t(u) + 2 d(u,p)\). Because \(|t(u) - t(p)| \leq d(u,p)\), it implies that \(t \geq t(p) + d(u,p)\). Assume by contradiction that \(d(p,q) < d(u,p)/2\). Then we would have \(t > t(p) + 2 d(p,q)\), hence the algorithm would have already matched \(p\) at time \(t(p) + 2 d(p,q)\) with \(q\) if it were not already matched. But we assumed that \(p\) got matched at time \(t > 2 d(p,q)\), hence the contradiction. Therefore \(d(p,q) \geq d(u,p)/2 = l_p \geq \min(l_p, l_q)\).

• Let \(p \in V_{req}\), we assume \(p\) got matched to some other request \(q\) so \(l_p = d(p,q)/2\). The TSP consists of two paths between \(p\) and \(q\). Given that we are in a metric graph, it follows that \(OPT_{TSP} \geq 2 d(p,q)\) and therefore \(l_p \leq \frac{1}{4} OPT_{TSP}\).

We can thus use 3: \[\begin{align} \sum l_p \leq \frac{1}{2}(\lceil \log n \rceil + 1) OPT_{TSP} \end{align}\] We remark that by the definition of \((l_p)\), the weight of every matching edge appears exactly twice (one for each endpoint) in \((l_p)\), therefore \(\sum 2 l_p = 2 w(M)\), so the overall connection cost satisfies: \[\begin{align} w(M) \leq \frac{1}{2}(\lceil \log n \rceil + 1) OPT_{TSP} \end{align}\]

We now consider the time cost \(\mathcal{W}_{GREEDY}\) of the algorithm. Let \(u\) and \(v\) be two requests matched together by the algorithm at time \(t\). Without loss of generality, let us assume that \(t(u) \leq t(v)\). Let \(t' = t(u) + 2d(u,v)\). We want to prove that \(t = t'\). By design of the algorithm, \(t \geq t(u) + 2d(u,v) = t'\). Moreover, we have \(t' \geq t(u) + d(u,v)\). Therefore using 1, both \(u\) and \(v\) have arrived at time \(t'\). We now consider the state of the algorithm at time \(t'\). If there were a request \(w\) closer to \(u\) than \(v\), the algorithm would immediately match \(u\) and \(w\) together as we would have \(t' > t(u) + 2d(u,w)\). This contradicts the fact that \(u\) and \(w\) got matched together. So at time \(t' = t(u) + 2d(u,v)\), \(u\) and \(v\) have both arrived and \(v\) is the closest request to \(u\), so the algorithm matches them together at that time, so \(t = t'\).

Thus, the time cost spent by \(u\) and \(v\) for waiting is \(t - t(u) + t - t(v) = 4d(u,v) + t(u) - t(v) \leq 4 d(u,v)\) because \(t(u) \leq t(v)\). So, the total time cost of the algorithm \(\mathcal{W}_{GREEDY}\) can be bounded by: \[\begin{align} \mathcal{W}_{GREEDY} &= \sum_{(u,v) \in M} 4d(u,v)\\ & = 4 w(M) \end{align}\]

Therefore, the total online cost of the greedy algorithm is at most: \[\begin{align} C_{GREEDY} &= w(M) + \mathcal{W}_{GREEDY} \\ & \leq w(M) + 4 \cdot w(M) = 5 \cdot w(M) \\ & \leq\frac{5}{2} (\lceil \log n\rceil + 1) OPT_{TSP} \end{align}\] ◻