Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Online regenerator placement
Mertzios, G.B.; Shalom, M.; Wong, P.W.H.; Zaks, S.
Authors
M. Shalom
P.W.H. Wong
S. Zaks
Abstract
Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem (Rlp), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online Rlp regarding the value of d and the number k of regenerators that can be used in any single node. (1) d is arbitrary and k unbounded. In this case a feasible solution always exists. We show an O(log|X|⋅ logd)-competitive randomized algorithm for any network topology, where X is the set of paths of length d. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of Ω( log(|E|/d)⋅logd log(log(|E|/d)⋅logd) ), where E is the edge set. (2) d = 2 and k = 1. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound 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.
Citation
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2016). Online regenerator placement. Theory of Computing Systems, 61(3), 739-754. https://doi.org/10.1007/s00224-016-9711-3
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 10, 2016 |
Online Publication Date | Sep 28, 2016 |
Publication Date | Sep 28, 2016 |
Deposit Date | Sep 12, 2016 |
Publicly Available Date | Sep 28, 2017 |
Journal | Theory of Computing Systems |
Print ISSN | 1432-4350 |
Electronic ISSN | 1433-0490 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 61 |
Issue | 3 |
Pages | 739-754 |
DOI | https://doi.org/10.1007/s00224-016-9711-3 |
Files
Accepted Journal Article
(215 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/s00224-016-9711-3
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