Resource allocation problems in multifiber WDM tree networks

Abstract

All-optical networks with multiple fibers lead to several interesting optimization problems. In this paper, we consider the problem of minimizing the total number of fibers necessary to establish a given set of requests with a bounded number w of wavelengths, and the problem of maximizing the number of accepted requests for given fibers and bounded number w of wavelengths. We study both problems in undirected tree networks T = (V, E) and present approximation algorithms with ratio 1 + 4|E| log |V |/OPT and 4 for the former and with ratio 2.542 for the latter. Our results can be adapted to directed trees as well.