Approximation algorithms for certain network improvement problems

We study budget constrained,network upgrading problems. Such problems aim a t finding optimal strategies for improving a network under some cost measur e subject to certain budget constraints. Given an edge weighted graph G = ( V, E), in the edge based upgrading model, it is assumed that each edge e of the given network also has an associated function c(e)(t) that specifies t he cost of upgrading the edge by an amount t. A reduction strategy specifie s for each edge e the amount by which the length e(e) is to be reduced, In the node based upgrading model, a node v can be upgraded at an expense of c (v). Such an upgrade reduces the delay of each edge incident on v, For a gi ven budget B, the goal is to find an improvement strategy such that the tot al cost of reduction is at most the given budget B and the cost of a subgra ph (e,g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. After provi ding a brief overview of the models and definitions of the various problems considered, we present several new results on the complexity and approxima bility of network improvement problems.