Summary: SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET /WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. Following previous work, we consider the problem where the route of each traffic stream is given as input, and we need to assign wavelengths so as to minimize the total number of used SONET ADMs. This problem is known to be NP-hard, and the best known approximation algorithm for this problem has a performance guarantee of \(\frac32\). We improve this result, and present a \(\frac{10}{7}\) algorithm. We also study some of the previously proposed algorithms for this problem, and give either tight or tighter analysis of their approximation ratio.
For the entire collection see [Zbl 1067.68010].