Complexity of Wavelength Assignment in Optical Network Optimization

We study the complexity of a spectrum of design problems for optical networks in order to carry a set of demands. Under wavelength division multiplexing (WDM) technology, demands sharing a common fiber are transported on distinct wavelengths. Multiple fibers may be deployed on a physical link. Our basic goal is to design networks of minimum cost, minimum congestion and maximum throughput. This translates to three variants in the design objectives: 1) Min-SumFiber: minimizing the total amount of fibers deployed to carry all demands; 2) Min-MaxFiber: minimizing the maximum amount of fibers per link to carry all demands; and 3) Max-Thruput: maximizing the carried demands using a given set of fibers. We also have two variants in the design constraints: 1) ChooseRoute: Here we specify both a routing path and a wavelength for each demand; 2) FixedRoute: Here we are given demand routes and we specify wavelengths only. The FixedRoute variant allows us to study wavelength assignment in isolation. Combining these variants, we have six design problems. In earlier work we have shown that general instances of the problems Min-SumFiber-ChooseRoute and Min-MaxFiber-FixedRoute have no constant-approximation algorithms. In this paper we prove that a similar statement holds for all four other problems. Our main result shows that Min-SumFiber- FixedRoute cannot be approximated within any constant factor unless NP-hard problems have efficient algorithms. This, together with the hardness of Min-MaxFiber-FixedRoute, shows that the problem of wavelength assignment is inherently hard by itself. We also study the complexity of problems that arise when multiple demands can be time-multiplexed onto a single wavelength (as in TWIN networks) and when wavelength converters can be placed along the path of a demand.