A network improvement problem under different norms

In this paper, we first consider a network improvement problem, called vertex-to-vertices distance reduction problem. The problem is how to use a minimum cost to reduce lengths of the edges in a network so that the distances from a given vertex to all other vertices are within a given upper bound. We use l(infinity), l(1) and l(2) norms to measure the total modification cost respectively. Under l(infinity) norm, we present a strongly polynomial algorithm to solve the problem, and under l(1) or weighted l(2) norm, we show that achieving an approximation ratio O( log(|V|)) is NP-hard. We also extend the results to the vertex-to-points distance reduction problem, which is to reduce the lengths of edges most economically so that the distances from a given vertex to all points on the edges of the network are within a given upper bound.