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

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...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2000-11, Vol.127 (1), p.189-202
Main Authors: Flippo, Olaf E., Kolen, Antoon W.J., Koster, Arie M.C.A., van de Leensel, Robert L.M.J.
Format: Article
Language:English
Subjects:
Dynamic programming
Optimization
Telecommunication networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(99)00340-9