## 1 Introduction  
### Background  
All-optical networks are used in scientific visualization, real-time medical imaging, video conferencing, high-speed supercomputing, distributed computing, in data centersand between them [1; 2]. This is due to the data rates offered by these networks which are several orders of magnitudes higher than those offered by other networks [2; 3; 4].  
**Wavelength division multiplexing:** To achieve these high data rates, all-optical networks maintain the signal in optical form. In other words, they avoid the optical-electronic-optical conversion overhead at the intermediate nodes which would otherwise have an adverse effect on the transmission rate. One of the main underlying technologies is _wavelength-division multiplexing_, which allows for the simultaneous transmission of signals over the same link, as long as they are transmitted on different wavelengths.  
**Switching cost:** The focus of early research on all-optical networks was to obtain efficient topologies and wavelength allocation schemes/algorithms to minimize the total number of used wavelengths. The work in [5] is an excellent survey of the main results in this direction. More recent research on these networks considers switching cost minimization as a major design goal. These works consider the capital expenses (CAPEX) and/or operational expenses (OPEX) (expenses that are independent of usage and depend on usage, respectively) incurred in all-optical networks by the basic electronic switching units, the most prominent of them being Add-Drop multiplexers (ADMs) and optical Add-Drop multiplexers (OADMs). Every lightpath is terminated by two ADMs. If two lightpaths with a common endpoint are assigned the same wavelength, they can share the ADM operating at this wavelength at the common endpoint. Similarly, two lightpaths sharing a common intermediate node that are assigned the same wavelength can share the OADM operating at that wavelength at the common node.  
**Grooming:** Typically, the transmission rates supported by a lightpath in an all-optical network is higher than the low-capacity demands. Consequently, a network operator puts together several low-capacity demands into one lightpath. This action of putting together is termed _grooming_, and the number \(g\) of communication requests that can be put together in a lightpath is termed the _grooming factor_. The grooming problem is the problem of assigning colors (wavelengths) to a given set of paths (communication requests) so that at every edge there are at most \(g\) of them assigned the same color. If a set of (at most \(g\)) lightpaths of the same wavelength have the same terminal node and terminal edge, they can share the ADM operating at that wavelength at that node (thus saving \(g-1\) ADMs). In addition, in a way similar to the non-grooming case (\(g=1\)), a second set of paths with the same terminal node but a different terminal edge can share the same ADM. As for OADMs, at most \(g\) lightpaths that are assigned the same wavelength share an OADM in a common intermediate node (thus saving \(g-1\) OADMs). The goal is to minimize the convex combination \(\alpha\cdot|OADMs|+(1-\alpha)\cdot|ADMs|\) of the number of ADMs and OADMs, for a fixed value \(\alpha\in[0,1]\). Clearly, our setting generalizes the well-studied ADM minimization problem (corresponding to the case of \(\alpha=0\)), as well as the OADM minimization one (corresponding to the case of \(\alpha=1\)).