کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430535 | 688024 | 2006 | 14 صفحه PDF | دانلود رایگان |
We study wavelength assignment in an optical network where each fiber has a fixed capacity of μ wavelengths. Given demand routes, we aim to minimize the maximum ratio between the number of fibers deployed on a link e and the number of fibers required on the same link e when wavelength assignment is allowed to be fractional. Our main results are negative ones. We show that there is no constant-factor approximation unless NP⊆ ZPP. In addition, unless NP ⊆ ZPTIME we show that there is no approximation for any γ∈(0,1) and no approximation for any γ∈(0,0.5) where m is the number of links in the network. Our analysis is based on the hardness of approximating the chromatic numbers. On the positive side, we present algorithms with approximation ratios , and O(Dmax) respectively, where Dmax is the length of the longest path.
Journal: Journal of Computer and System Sciences - Volume 72, Issue 1, February 2006, Pages 118-131