Inapproximability and a polynomially solvable special case of a network improvement problem

We consider a network improvement problem in which we wish to spend as little as possible to ensure that the distances from a given vertex to all other vertices are within given bounds. We first prove that achieving an approximation ratio (1+ε) is NP-hard for some constant ε>0. Then we show that the problem can be solved by a combinatorial algorithm running in O(|V|log|V|) time when the network is restricted to a tree.