## 4 Approximation Algorithms
### _Groom-Oadm: An Algorithm for the Minimization of OADMs in Edge Instances_  
Algorithm Groom-OADM, whose pseudo-code is given in Algorithm 2, processes the requests in the non-increasing order of their lengths and partitions the ordered requests into \(\lceil\frac{m}{g}\rceil\) sets of \(g\) requests with the possible exception of the last set that may contain less than \(g\) requests. Each such set is colored with a unique color.  
Lemma 1: _Groom-Oadm is a two-approximation edge-algorithm for the minimization of OADMs._  
Proof.: _Correctness and running time:_ The algorithm produces a valid output since every color \(\lambda\) is assigned to at most \(g\) requests. The running time of the algorithm is dominated by the the running time of the sorting phase and is thus polynomial in the size of the instance which, in our case, is dominated by the number \(|P|\) of requests in the instance.  
_Approximation ratio:_ Let \(k=\lceil\frac{m}{g}\rceil\) be the number of colors used by the algorithm. Since all the requests share an edge of the chain, any one-colorable set contains at most \(g\) of them. Therefore, any solution, in particular an optimal one, uses at least \(k\) colors. Denote by \(p_{\lambda}\) the longest path of the set \(P_{\lambda}\) of the paths colored \(\lambda\) by Groom-OADM. Consider an optimal coloring, and rename its colors in the following way. The color assigned to the longest path is 0. The color assigned to the longest path that is not assigned the color 0 is 1, the color assigned to the longest path that is not assigned the colors 0 or 1 is 2, and so on. It it easy to show by induction on \(\lambda\) that for every \(\lambda\), there is at least one path whose length is at least the length \(\ell(p_{\lambda})\) of \(\lambda\). Therefore, an optimal solution uses at least \(\ell(p_{\lambda})-1\) OADMs operating at color \(\lambda\). On the other hand, Groom-OADM uses at most \(2(\ell(p_{\lambda})-1)\) OADMs since all the paths have an edge in common. Summing up, with all colors \(\lambda\in[k]\), we conclude the proof.  
In the following, we exploit the result of Lemma 1 in order to obtain an approximation algorithm for the CombinedTrafficGrooming problem. By combining Lemma 1 with Theorem 2, we are also able to derive the following theorem providing an approximation algorithm for the case \(\alpha=1\); moreover, it is worth noticing that a better approximation ratio of 4 is given in [28] for this particular case.  
```
0:\((G,P,g,1)\) is an edge instance of CombinedTrafficGrooming.
0: Return an two-approximate solution of \((G,P,g,1)\):
1:\(P^{\prime}\leftarrow\) the paths of \(P\) sorted in non-increasing order of their lengths.
2:\(\lambda=0\).
3:while\(P^{\prime}\
eq\emptyset\)do
4:\(P_{\lambda}\) the first \(\min\{|P^{\prime}|,g\}\) paths of \(P^{\prime}\).
5:\(P^{\prime}\gets P\setminus P_{\lambda}\).
6: Color the paths of \(P_{\lambda}\) with color \(\lambda\).
7:\(\lambda++\);
8:endwhile
```  
**Algorithm 2**Groom-OADM.  
**Theorem 3**.: _Merge(Groom-OADM) is a \(2\lceil\log n\rceil\) (and, respectively, \(2(\lceil\log n\rceil+1)\)) approximation algorithm for CombinedTrafficGrooming in a chain (and, respectively, ring) topology with \(\alpha=1\), (i.e., for the problem of minimizing the number of OADMs)._