A depth-first dynamic programming procedure for the extended tree knapsack problem in local access network design

The Extended Tree Knapsack Problem (ETKP) is a generalized version of the Tree Knapsack Problem where an arbitrary nonlinear traffic-flow cost is imposed. This problem can be solved by the straight-forward ‘bottom-up’ approach with a time complexity of O(nH²), where n is the number of nodes in the tree, and H is the knapsack capacity. In this paper, we show that if the traffic-flow cost function is the cable expansion cost, which occurs in the Local Access Telecommunication Network (LATN) expansion, this special ETKP can be solved by a depth-first dynamic programming procedure in a time complexity of O(n δ H), where δ is the largest existing cable capacity in LATN. This result indicates that the depth-first dynamic programming algorithm can be applied for solving a general class of tree optimization problems. The computational results of our algorithm for the ETKP are also provided.