Minimizing maximum fiber requirement in optical networks

摘要

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(npolylogn) we show that there is no logγμ approximation for any γ∈(0,1) and no logγm 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 O(logm+logμ), O(logDmax+logμ) and O(Dmax) respectively, where Dmax is the length of the longest path.