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.
Versions