Best location of service centers in a treelike network under budget constraints (Q2639769)

Consider a tree network with a weight (population) and a cost (to set up a service center) associated with each vertex. Any center will service both the vertex at which it lies and its adjacent vertices. The aim is to locate service centers so that total setup cost remains within a given budget, and maximising the total population served. This problem is shown to be NP-hard in general. For the case where all setup costs are equal a polynomial dynamic programming algorithm is derived. For the general case two pseudopolynomial methods are given, one by way of traditional dynamic programming, the second, more efficient one, by way of a modified left-right dynamic programming method.