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