Approximation algorithms for routing and call scheduling in all-optical chains and rings

We study the problem of routing and scheduling requests of limited durations in an all-optical network. The task is servicing the requests, assigning each of them a starting time and a wavelength, with restrictions on the number of available wavelengths. The goal is minimizing the overall time needed to serve all requests. We propose constant approximation algorithms for both ring and chain networks. In doing this, we also propose a polynomial-time approximation scheme for the problem of routing weighted calls on a directed ring with minimum load. © 2002 Elsevier Science B.V. All rights reserved. © 2002 Elsevier Science B.V. All rights reserved.