Template-type: ReDif-Paper 1.0
Author-Name: Leensel R.L.M.J. van de
Author-Name: Flippo O.E.
Author-Name: Koster A.M.C.A.
Author-workplace-name: METEOR
Title: A Dynamic Programming Algorithm for the ATM Network Installation Problem on a Tree
Abstract: This paper considers the ATM Network Installation Problem on a tree. To install such a communication network, decisions concerning the location of hardware devices, the capacity installation on links, and the routing of demands have to be made simultaneously. The problem is shown to be NP-hard. By exploiting the tree structure we show that the problem can be solved to optimality using a pseudo-polynomial time dynamic programming algorithm. Computational experiments on real-life problem instances indicate that the algorithm is highly efficient.
Keywords: Economics ; 
Series: Research Memoranda
Creation-Date: 1998
Number: 004
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:d65e4f2f-5767-4bb3-8140-9b52dfb1b2ab/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 376874
Handle: RePEc:unm:umamet:1998004