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 l8, 11 and 12 norms to measure the total modification cost respectively. Under l8 norm, we present a strongly polynomial algorithm to solve the problem, and under l1 or weighted l2 norm, we show that achieving an approximation of 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 the 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.