Article ID: | iaor20011826 |
Country: | Netherlands |
Volume: | 127 |
Issue: | 1 |
Start Page Number: | 189 |
End Page Number: | 202 |
Publication Date: | Nov 2000 |
Journal: | European Journal of Operational Research |
Authors: | Flippo Olaf E., Kolen Antoon W.J., Koster Arie M.C.A., Leensel Robert L.M.J. van de |
Keywords: | programming: dynamic, networks |
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