On minimizing the number of ADMs in WDM/SONET rings

the dominant cost factor in the WDM
(Wavelength Division Multiplexing)/SONET rings. The number of SONET ADMs
required by a set of traffic streams is determined by the lightpath
routing and
wavelength assignment of the traffic streams. We address the WDM/SONET
ring network design problem
where each traffic stream has a predetermined routing given by a
lightpath, and a careful wavelength
assignment for the ligthpaths is used to
minimize the number of SONET ADMs. This can be modeled as the problem
of partitioning of a set of circular arcs over a ring into segments
of non-intersecting arcs where the objective is to minimize the number
of non-circle segments. We present and analyse
two randomized approximation algorithms.
These significantly improve on known results add to novel
approximation techniques.