Minimizing maximum fiber requirement in optical networks

We study wavelength assignment in an optical network where each fiber has a fixed capacity of mu 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 subset of ZPP. In addition, unless NP subset of ZPTIME(n(polylog n)) we show that there is no log(gamma) p approximation for any gamma is an element of (0, 1) and no log(gamma) m approximation for any gamma is an element of (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 (log m + log mu), O (log D-max + log mu) and O (D-max) respectively, where D-max is the length of the longest path. (c) 2005 Elsevier Inc. All rights reserved.