Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Placing regenerators in optical networks to satisfy multiple sets of requests
Mertzios, G.B.; Sau, I.; Shalom, M.; Zaks, S.
Authors
I. Sau
M. Shalom
S. Zaks
Contributors
Samson Abramsky
Editor
Cyril Gavoille
Editor
Claude Kirchner
Editor
Friedhelm Meyer auf der Heide
Editor
Paul G. Spirakis
Editor
Abstract
The placement of regenerators in optical networks has become an active area of research during the last 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. While most of the research has focused on heuristics and simulations, the first theoretical study of the problem has been recently provided in [10], where the considered cost function is the number of locations in the network hosting regenerators. Nevertheless, in many situations a more accurate estimation of the real cost of the network is given by the total number of regenerators placed at the nodes, and this is the cost function we consider. 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 ≥ 2 it does not admit a PTASUnknown control sequence '\textsc', even if G has maximum degree at most 3 and the lightpaths have length O(d)(d). We complement this hardness result with a constant-factor approximation algorithm with ratio ln (d ·p). We then study the case where G is a path, proving that the problem is NP-hard for any d,p ≥ 2, even if there are two edges of the path such that any lightpath uses at least one of them. Interestingly, we show that the problem is polynomial-time solvable in paths when all the lightpaths share the first edge of the path, as well as when the number of lightpaths sharing an edge is bounded. Finally, we generalize our model in two natural directions, which allows us to capture the model of [10] as a particular case, and we settle some questions that were left open in [10].
Citation
Mertzios, G., Sau, I., Shalom, M., & Zaks, S. (2010). Placing regenerators in optical networks to satisfy multiple sets of requests. In S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, & P. G. Spirakis (Eds.), Automata, Languages and Programming : 37th International Colloquium, ICALP 2010, 6-10 July 2010, Bordeaux, France ; proceedings, Part II (333-344). https://doi.org/10.1007/978-3-642-14162-1_28
Conference Name | 37th International Colloquium on Automata, Languages and Programming (ICALP) |
---|---|
Conference Location | Bordeaux, France |
Publication Date | Jul 1, 2010 |
Deposit Date | Dec 8, 2011 |
Publicly Available Date | Jun 22, 2015 |
Pages | 333-344 |
Series Title | Lecture notes in computer science |
Series Number | 6199 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Automata, Languages and Programming : 37th International Colloquium, ICALP 2010, 6-10 July 2010, Bordeaux, France ; proceedings, Part II. |
DOI | https://doi.org/10.1007/978-3-642-14162-1_28 |
Keywords | Optical networks, Regenerators, Overprovisioning, Approximation algorithms, Hardness of approximation. |
Public URL | https://durham-repository.worktribe.com/output/1158196 |
Additional Information | This research was supported by the Israel Science Foundation (grant No. 1249/08) and by the British Council (grant No. UKTELHAI09). Proccedings published as: Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II Event url: http://icalp10.inria.fr/ |
Files
Accepted Conference Proceeding
(326 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-14162-1_28.
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search