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.
inapproximability network flows shortest path maximum 3-satisfiability