Vijay Kumar and Atri Rudra

Approximation Algorithms for Wavelength Assignment

Abstract : Winkler and Zhang introduced the FIBER MINIMIZATION problem. They showed that the problem is NP-complete but left the question of approximation algorithms open. We give a simple 2-approximation algorithm for this problem. We also show how ideas from the Dynamic Storage Allocation algorithm of Buchsbaum et al. can be used to give an approximation ratio arbitrarily close to 1 provided the problem instance satisfies certain criteria. We also show that these criteria are necessary to obtain an approximation scheme. Our 2-approximation algorithm achieves its guarantee unconditionally. We also consider the extension of the problem to a ring network and give a 2+o(1)-approximation algorithm for this topology. Our techniques also yield a factor-2 approximation for the related problem of PACKING INTERVALS IN INTERVALS, also introduced by Winkler and Zhang.