Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems

Given a source node and a family D of subsets of nodes of a WDM optical network, the multicasting to groups (MG) problem is to find a set of paths from the source to at least one node in each subset in D, and an assignment of wavelengths to paths so that paths sharing an optical link are assigned different wavelengths. The goal is to minimize the total number of used wavelengths. We note that MG is closely related to several important combinatorial optimization problems. These include set cover and some useful generalizations of it, that correspond to MG when the network is a tree. From the equivalence between MG and set cover it follows that unless NP ⊂ DTIME(nlog log n), MG cannot be approximated within a logarithmic factor. On the positive side, we give polynomial time approximation algorithms for the MG problem. Our algorithm has a guaranteed approximation factor matching the non-approximability bound in case of tree networks.