## 4 Approximation Algorithms
### The Merge Meta Algorithm  
Consider the following meta algorithm Merge whose pseudo-code is given in Algorithm 1. It receives an \(r\)-approximation algorithm \(\mathcal{EA}\) for edge instances of CombinedTrafficGrouping and acts on an arbitrary instance \((G,P,g,\alpha)\) of CombinedTrafficGrouping. At the first step, the set \(\overline{P}\) of all requests sharing the median edge of the chain are given as input to \(\mathcal{EA}\) to obtain a coloring \(\overline{W}\) of these requests. The algorithm then splits the chain \(G\) into two sub-chains \(G_{1}\) and \(G_{2}\) by removing the median edge and recursively proceeds on these sub-chains. The colorings returned from the recursive invocations are modified so that they do not use the colors of \(\overline{W}\). ```
0:\(\mathcal{EA}\) is an \(r\)-approximation algorithm for edge instances of CombinedTrafficGrouping. 0:\((G,P,g,\alpha)\) an instance of CombinedTrafficGrouping. 0:\(G\) is a chain with vertices \(i,i+1,\ldots,j\). 0:Return an \(r\lceil\log n\rceil\)-approximate solution of \((G,P,g,\alpha)\)
1:\(k\leftarrow\lfloor\frac{i+j}{2}\rfloor\). 2:\(\overline{P}\leftarrow\{p\in P\ |\ \ p\ \text{contains the edge }\{k,k+1\}\). 3:\(\overline{W}\leftarrow\mathcal{EA}(G,\overline{P},g,\alpha)\). 4:\(G_{1}\leftarrow\) the sub-chain of \(G\) with vertices \(i,\ldots,k\). 5:\(G_{2}\leftarrow\) the sub-chain of \(G\) with vertices \(k+1,\ldots,j\). 6:for\(\ell\in\{1,2\}\)do
7:if\(P_{\ell}\
eq\emptyset\)then
8:\(P_{\ell}\leftarrow\{p\in P\ |\ \ p\ \text{is completely in }G_{\ell}\}\). 9:\(W_{\ell}\leftarrow\textsc{Merge}(\mathcal{EA},G_{\ell},P_{\ell},g,\alpha)\). 10: Add \(\left|\overline{W}\right|\) to every color of \(W_{\ell}\). 11:else
12:\(W_{\ell}\leftarrow\emptyset\). 13:endif
14:endfor
15:return\(\overline{W}\cup W_{1}\cup W_{2}\). ```  
**Algorithm 1**Merge. In ring networks, we add an initial invocation of \(\mathcal{EA}\) on all the requests sharing some arbitrary edge of the ring and then proceed on the remaining chain instance. The following theorem shows the correctness and the approximation ratio guaranteed by Merge. Theorem 4.1: _If \(\mathcal{EA}\) is an \(r\)-approximation algorithm for edge instances, then Merge and its modification for ring topologies guarantee approximation ratios \(r\lceil\log n\rceil\) and \(r(\lceil\log n\rceil+1)\), respectively._  
Proof. : We prove by induction on the depth of the recursion. _Correctness and running time:_ If there are no recursive invocations, the correctness of Merge directly follows from the one of \(\mathcal{EA}\). Otherwise, by the inductive hypothesis and by the correctness of \(\mathcal{EA}\), the colorings \(W_{1}\) and \(W_{2}\) are valid. The paths in \(P_{1}\) and \(P_{2}\) do not overlap and they are colored with colors different than those of \(\overline{W}\). Therefore, the returned coloring \(\overline{W}\cup W_{1}\cup W_{2}\) is valid. We observe that algorithm \(\mathcal{EA}\) is invoked at most \(n\) times, and thus Merge is a polynomial-time algorithm. _Approximation ratio:_ Since the depth of the recursion is at most \(\lceil\log n\rceil\), it is sufficient to prove by induction on the depth \(d\) of the recursion that Merge is a \(d\times r\)-approximation algorithm. If \(d=1\), then the execution consists of one invocation of \(\mathcal{EA}\) and the result follows. Otherwise, consider an execution where the depth of the recursion is \(d>1\). Let \(m^{*}\) be the cost of an optimal solution, and let \(m_{1}^{*}\), \(m_{2}^{*}\) and \(\overline{m}^{*}\) be the cost of optimal solutions of \(P_{1},P_{2}\) and \(\overline{P}\), respectively. Clearly, \(m^{*}\geq\overline{m}*\). Furthermore, \(m^{*}\geq m_{1}^{*}+m_{2}^{*}\) since the sets \(P_{1}\) and \(P_{2}\) do not overlap, thus no ADM sharing or OADM sharing is possible between the instances. As for the solution of the algorithm, let \(m\) be the cost of the solution returned by Merge, and let \(m_{1},m_{2}\) and \(\overline{m}\) be the costs of \(W_{1},W_{2}\) and \(\overline{W}\), respectively.