_algorithms_  
_Article_  
**The Traffic Grooming Problem in Optical Networks**  
**with Respect to ADMs and OADMs: Complexity**  
**and Approximation \({}^{\dagger}\)**  
**[PERSON] \({}^{1}\), [PERSON] \({}^{2}\), [PERSON] \({}^{3}\), [PERSON] \({}^{4,*}\)\({}^{\copyright}\) and [PERSON] \({}^{5,6}\)**  
\({}^{1}\) GSSI Institute, [PERSON] 7, 67100 L'Aquila, Italy; [EMAIL_ADDRESS]  
\({}^{2}\) Department of Information Engineering Computer Science and Mathematics, University of L'Aquila, 67100 L'Aquila, Italy; [EMAIL_ADDRESS]  
\({}^{3}\) Dipartimento di Economia, University of Chieti-Pescara, Viale Pindaro 42, 65125 Pescara, Italy; [EMAIL_ADDRESS]  
\({}^{4}\) Department of Computer Science, Tel-Hai Academic College, Upper Galilee 1220800, Israel  
\({}^{5}\) Department of Computer Science, Technion, Haifa 320003, Israel; [EMAIL_ADDRESS]  
\({}^{6}\) Member of the Academic Council, Ort Braude College, Karmiel 2161002, Israel  
\({}^{*}\) Correspondence: [EMAIL_ADDRESS]  
\({}^{\dagger}\) A preliminary version of this paper appeared in the Proceedings of the 14 th International European Conference on Parallel and Distributed Computing (Euro-Par), 2008. This paper has been significantly extended since then. Some of the major additions, besides the inclusion of all the proofs (that were only sketched or omitted in the conference version) of the technical contribution, are an extension of the results holding for the path topology to the more interesting setting of ring topology and an improved presentations of the results also including pseudo-code for algorithms, more figures and a more in-depth comparison with the related literature. This research was supported by the Israel Science Foundation, grant NO. 1249/08 and by the Italian MIUR PRIN 2017 Project ALGADIMAR \"Algorithms, Games, and Digital Markets\" (2017R9 FHRS_002).  
**Abstract** All-optical networks transmit messages along lightpaths in which the signal is transmitted using the same wavelength in all the relevant links. We consider the problem of switching cost minimization in these networks. Specifically, the input to the problem under consideration is an optical network modeled by a graph \(G\), a set of lightpaths modeled by paths on \(G\), and an integer \(g\) termed the _grooming factor_. One has to assign a wavelength (modeled by a color) to every lightpath, so that every edge of the graph is used by at most \(g\) paths of the same color. A lightpath operating at some wavelength \(\lambda\) uses one Add/Drop multiplexer (ADM) at both endpoints and one Optical Add/Drop multiplexer (OADM) at every intermediate node, all operating at a wavelength of \(\lambda\). Two lightpaths, both operating at the same wavelength \(\lambda\), share the ADMs and OADMs in their common nodes. Therefore, the total switching cost due to the usage of ADMs and OADMs depends on the wavelength assignment. We consider networks of ring and path topology and a cost function that is a convex combination \(\alpha\cdot|OADMs|+(1-\alpha)|ADMs|\) of the number of ADMs and the number of OADMs deployed in the network. We showed that the problem of minimizing this cost function is NP-complete for every convex combination, even in a path topology network with \(g=2\). On the positive side, we present a polynomial-time approximation algorithm for the problem.  
**Keywords:** optical networks; wavelength division multiplexing (WDM); Add-Drop Multiplexer (ADM); Optical Add-Drop Multiplexer (OADM); traffic grooming; path and ring networks