.png){kind=icon}
返回
A dynamic programming algorithm for the local access telecommunication network expansion problem
.png){kind=icon}
PRE
AI
DOI：10.1016/S0377-2217(99)00340-9.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
dynamic programming
telecommunication networks
optimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏
分享收藏
查看更多内容