We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Placing regenerators in optical networks to satisfy multiple sets of requests.

Mertzios, G.B. and Sau, I. and Shalom, M. and Zaks, S. (2012) 'Placing regenerators in optical networks to satisfy multiple sets of requests.', IEEE/ACM transactions on networking., 20 (6). 1870-1879 .


The placement of regenerators in optical networks has become an active area of research during the last few years. 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 lightpath there are no more than $d$ hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini (IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498–511, Apr. 2011). Furthermore, in our model we assume that 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. While this problem can be easily solved when $d=1$ or $p=1$, we prove that for any fixed $d,p geq 2$, it does not admit a PTAS, even if $G$ has maximum degree at most 3 and the lightpaths have length $ {cal O}(d)$. We complement this hardness result with a constant-factor approximation algorithm with ratio $ln (d cdot p)$. We then study the case where $G$ is- a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flammini as a particular case, and we settle some questions that were left open therein.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Date accepted:No date available
Date deposited:23 June 2015
Date of first online publication:December 2012
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar