Online Lower Bounds and Offline Inapproximability in Optical Networks

摘要

We present lower bounds and inapproximability results for optimization problems that originated in studies of optical networks. They include offline and online scenarios, and concern problems that optimize the use of components in the optical networks, specifically Add-Drop Multiplexers (ADMs) and regenerators. First we discuss the online version of the problem of minimizing the number of ADMs in optical networks. In this case lightpaths need to be colored such that overlapping paths get different colors, path that share an endpoint can get the same color, and the cost is the total number endpoints (=ADMs); the key point is that an endpoint shared by two same-colored paths is counted only once. Following [19] (where we showed tight competitive ratios for several networks), we present in this paper a 3/2 lower bound on the competitive ratio for a path network. We next present problems that deal with the use of regenerators in optical networks. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any light-path there are no more than d hops without meeting a regenerator. We first discuss the online version of the problem of optimizing the number of locations where regenerators are placed, following [17]. When there is a bound on the number of regenerators in a single node, there is not necessarily a solution for a given input. We distinguish between feasible inputs and infeasible ones. For the latter case our objective is to satisfy the maximum number of lightpaths. For a path topology we consider the case where d = 2, and show a lower bound of {the square root of}l/2 for the competitive ratio (where l is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs. Last we study the problem where we are given a finite set of p possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied (that is, regenerators are placed such that in any lightpath there are no more than d hops without meeting a regenerator). We prove - following [16] - that the problem does not admit a PTAS for any d,p ≥ 2. Some of these problems have interesting implications to problems stated within scheduling theory.