Traffic Grooming in a Passive Star WDM Network

We consider the traffic grooming problem in passive WDM star networks. Traffic grooming is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. We first prove that the traffic grooming problem in star networks is NP-hard for a more restricted case than the one considered in [2]. Then, we propose a polynomial time algorithm for the special case where there are two wavelengths per fiber using matching techniques. Furthermore, we propose two reductions of our problem to two combinatorial optimization problems, the constrained multiset multicover problem [3], and the demand matching problem [4] allowing us to obtain a polynomial time H_2C (resp. $2+\frac{4}{5}$) approximation algorithm for the minimization (resp. maximization) version of the problem, where C is the capacity of each wavelength.