## 4 Approximation Algorithms
### Groom: An Algorithm for Edge Instance of CombinedTrafficGrooming  
Algorithms obtained from Groom-OADM with a slight modification. In the sort phase in which the paths are sorted by their lengths, Groom keeps sets of identical paths together. **Lemma 2**. : _Groom is a \(2\sqrt{8}\)-approximation edge-algorithm for CombinedTrafficGrooming._  
Proof. : Clearly, every execution of Groom is an execution of Groom-OADM. Therefore, by Lemma 1, Groom is a two-approximation edge-algorithm for the OADM minimization problem. In the following, we show that Groom is a \(2\sqrt{8}\)-approximation algorithm for the ADM minimization problem. As the combined cost is a convex combination of ADM and OADM costs, this implies the Lemma. Let \(W^{*}\) be the number of colors used by some optimal solution. For \(1\leq\lambda\leq W^{*}\), let \(P^{*}_{\lambda}\) be the set of paths colored \(\lambda\) by this solution. Notice that \(P=\uplus_{\lambda=1}^{W^{*}}P^{*}_{\lambda}\) (where \(\uplus\) is the union operation on multisets). Let \(\overline{P^{*}_{\lambda}}\subseteq P^{*}_{\lambda}\) be such that from every set of identical paths of \(P^{*}_{\lambda}\), exactly one is in \(\overline{P^{*}_{\lambda}}\). Let also: \(\overline{P^{*}}=\uplus_{\lambda=1}^{W^{*}}\overline{P^{*}_{\lambda}}\). Recall that we consider edge instances, in which all the paths share a common edge \(e\). Every path has one endpoint at each side of \(e\). Then, any subset of paths can be considered as the edge set of a bipartite graph \((U,V,E)\). Specifically, \(U\) (resp. \(V\)) is the set of nodes on the left (resp. right) of \(e\) (including one endpoint of \(e\)). Every path of \(P\) with endpoints \(u\in U\) and \(v\in V\) corresponds to an edge \(\{u,v\}\in E\). As \(\overline{P^{*}_{\lambda}}\) does not contain identical paths, it induces a simple bipartite graph. A simple bipartite graph \((U,V,E)\) satisfies \(|E|\leq|U||V|\). For fixed \(|U\cup V|\) this is maximized when \(|U|=|V|=\frac{|U\cup V|}{2}\). Therefore, the number \(ADM^{*}_{\lambda}\) of ADMs colored \(\lambda\) used by this solution satisfies \(\left|\overline{P^{*}_{\lambda}}\right|\leq\left(\frac{ADM^{*}_{\lambda}}{2} \right)^{2}\). Then, \(ADM^{*}_{\lambda}\geq 2\sqrt{|\overline{P^{*}_{\lambda}}|}=2\frac{|\overline{P^{*}_{ \lambda}}|}{\sqrt{|\overline{P^{*}_{\lambda}}|}}\geq 2\frac{|\overline{P^{*}_{\lambda}}|}{ \sqrt{8}}\). By summing up over all colors, we obtain \(ADM^{*}\geq\frac{2|\overline{P^{*}}|}{\sqrt{8}}\). Let \(W\) be the number of colors used by the solution returned by 6. For \(1\leq\lambda\leq W\), let \(P_{\lambda}\) be the set of paths colored \(\lambda\) by this solution. Notice that, also in this case, it clearly holds that \(P=\uplus_{\lambda=1}^{W}P_{\lambda}\). Let \(\overline{P_{\lambda}}\subseteq P_{\lambda}\) be such that from each (maximal) set of identical paths, exactly one path is in \(\overline{P_{\lambda}}\). Let also \(\overline{P}=\uplus_{\lambda=1}^{W}\overline{P_{\lambda}}\). Consider a maximal nonempty set \(X\) of identical paths. Any solution must use at least \(\left\lceil\frac{|X|}{s}\right\rceil\) different colors for these paths. In particular, this holds for our optimal solution. In other words, \(\left|X\cap\overline{P^{*}}\right|\geq\left\lceil\frac{|X|}{g}\right\rceil\). 6 divides \(X\) into subsets of size \(g\), except possibly the first and last sets. Therefore, \(\left|X\cap\overline{P}\right|\leq\left\lceil\frac{|X|}{g}\right\rceil+1\leq 2 \left\lceil\frac{|X|}{g}\right\rceil\leq 2\left|X\cap\overline{P^{*}}\right|\). Summing up for all such sets \(X\), we obtain \(\left|\overline{P}\right|\leq 2|\overline{P^{*}}|\). On the other hand, a solution returned by 6, uses at most 2 ADMs per each path in \(\overline{P}\). The remaining paths use these ADMs at no additional cost. Therefore, the number of ADMs used by 6 satisfy \(ADM\leq 2|\overline{P}|\leq 4|\overline{P^{*}}|\leq 2\sqrt{g}ADM^{*}\). The following theorem is a direct consequence of the previous Lemma and Theorem 3.