## 2 Problem Definition  
Let \(G=(V,E)\) be an undirected graph with \(n=|V|\) nodes, modeling the optical network. A _coloring_ (or _wavelength assignment_) \(w\) of a set \(P\) of simple paths in a graph is a function \(w:P\to\mathbb{N}^{+}=\{1,2,\ldots\}\). A coloring \(w\) of \(P\) is \(g\)-_proper_ if for every edge \(e\in E\) and every color \(\lambda\in\mathbb{N}^{+}\), the number of paths \(p\in P\) such that \(w(p)=\lambda\) and \(e\) is an edge of \(p\) is at most \(g\).  
A path \(p\) of length \(l(p)\) between two nodes \(u\) and \(v\) uses an ADM operating at wavelength \(w(p)\) at each of its endpoints, namely at \(u\) and \(v\). Moreover, such a path uses an OADM operating at wavelength \(w(p)\) at each of its intermediate nodes. Overall, such a path uses two ADMs and \(l(p)-1\) OADMs.  
Given a \(g\)-proper coloring \(w\) of a set of paths \(P\), an ADM operating at a wavelength \(\lambda\) at some node \(v\) may serve all the paths terminating at \(v\) and colored \(\lambda\), provided that they enter \(v\) via at most two edges. Therefore, an \(ADM\) may serve at most \(2g\) paths.  
Similarly, an OADM operating at a wavelength \(\lambda\) at some node \(v\) with two incident edges serves all the paths having \(v\) as an internal node and colored \(\lambda\). In general, i.e., when the degree of such a node \(v\) is at least three, such an OADM may serve a set of paths having\(v\) as an internal node and colored \(\lambda\), provided that they enter and leave \(v\) via the same pair of edges. Therefore, an \(OADM\) may serve at most \(g\) paths.  
Summarizing, in a path or ring topology, the number \(ADM^{w}_{v,\lambda}\) of ADMs operating at wavelength \(\lambda\) at node \(v\) is one if there is a path colored \(\lambda\) terminating at \(v\), and zero otherwise. The number \(OADM^{w}_{v,\lambda}\) of OADMs operating at wavelength \(\lambda\) at node \(v\) is one if there is a path colored \(\lambda\) having \(v\) as an internal node, and zero otherwise. See Figure 1 for an example.  
In a general network, if the number of edges incident to \(v\) that are used by paths ending at \(v\) and colored \(\lambda\) is \(d\), then the number \(ADM^{w}_{v,\lambda}\) of ADMs operating at wavelength \(\lambda\) at node \(v\) is \(\lceil\frac{d}{2}\rceil\). Similarly, the number \(OADM^{w}_{v,\lambda}\) of OADMs operating at wavelength \(\lambda\) at node \(v\) is equal to the number of edge pairs incident to \(v\) that are used by paths crossing \(v\) and colored \(\lambda\). \(ADMs^{w}\) (resp. \(OADMs^{w}\)) is the number of \(ADMs\) (resp. \(OADMs\)) needed by a \(g\)-proper coloring \(w\), i.e., the sum of \(ADM^{w}_{v,\lambda}\) (resp. \(OADM^{w}_{v,\lambda}\)) over all nodes \(v\) and all colors \(\lambda\).  
We are now ready to formally define the problem under consideration.  
CombinedTrafficGrouping  
**Input**: \((G,P,g,\alpha)\) where \(G\) is a graph, \(P\) is a multiset of paths on \(G\), \(g\) is a positive integer and \(\alpha\in[0,1]\).  
**Output**: A \(g\)-proper coloring of \(P\).  
**Objective:** Minimize \(COST(w)=\alpha\times OADMs^{w}+(1-\alpha)\times ADMs^{w}\).  
Figure 1: An input example on a chain network with 13 nodes and \(g=3\) at the top. Below are two possible colorings of the input paths. Both colorings use two colors. In the first coloring, the paths colored with \(\lambda=1\) use 5 ADMs (at nodes 1, 5, 8, 9 and 11) and 9 OADMs (at nodes 2, 3, 4, 5, 6, 7, 8, 9 and 10). The paths colored \(\lambda=2\) use 6 ADMs and 11 OADMs. This coloring uses 11 ADMs and 20 OADMs in total. On the other hand, the second coloring uses 10 ADMs and 18 OADMs in total.