logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

A dynamic programming algorithm for the local access telecommunication network expansion problem

delete2000-11-01
delete13
PRE
AI
O
Olaf E. Flippo
K
Kolen, AWJ
A
Arie M. C. A. Koster
V
van de Leensel, RLMJ
DOI：10.1016/S0377-2217(99)00340-9delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
In this paper we consider the local access telecommunication network expansion problem, in which growing demand can be satisfied by expanding cable capacities and/or installing concentrators in the network. The problem is known to be NP-hard. We prove that the problem is weakly NP-hard, and present a pseudo-polynomial dynamic programming algorithm for the problem, with time complexity O(nB(2)) and storage requirements O(nB), where n refers to the size of the network, and B to an upper bound on concentrator capacity. The cost structure in the network is assumed to be decomposable, but may be non-convex, non-concave, and node and edge dependent otherwise. This allows for incorporation of many aspects occurring in practical planning problems. Computational results indicate that the algorithm is very efficient and can solve medium to large scale problems to optimality within (fractions of) seconds to minutes. (C) 2000 Elsevier Science B.V. All rights reserved.
Keywords:
dynamic programming
telecommunication networks
optimization
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

European Journal of Operational Research cover
European Journal of Operational Research
IF:
6
Papers:
2.2W
Citations:
6.4W

Organization

No organization information available