| Abstract: |
We present a polynomial-time greedy algorithm that assigns proper wavelengths to a set of requests of maximum load L per directed fiber link on a directed fiber tree using at most
5/3L wavelengths. This improves previous results of Raghavan and Upfal (Proc. Ann. ACM Symp. on theory of computing STOC, 1994, pp. 134-143), Mihail et al. (Proc. 36th IEEE Symp. on
Foundations of Computer Science, 1995, pp. 548-557), Kaklamanis and Persiano (Proc. Algorithms - ESA 96, Lecture Notes in Computer Science, 1136, pp. 460-470), Kumar and Schwabe (Proc. 8th Ann.
ACM-SIAM Symp. on Discrete Algorithms SODA, 1997, pp. 437-444). We also prove that no greedy algorithm can in general use less than 5/3L wavelengths for a set of requests of load L
in a directed fiber tree, and thus our algorithm is optimal in the class of greedy algorithms which includes the algorithms presented in [8-10,12]. |
