Optimal strategies for upgrading networks

摘要

We study (ital budget constrained optimal network upgrading problems). Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an edge weighted graph (ital G(V,E)), in the (ital edge based upgrading model), it is assumed that each edge (ital e) of the given network has an associated function (ital c(e)) that specifies for each edge (ital e) the amount by which the length (ital l(e)) is to be reduced. In the (ital node based upgrading model) a node (ital v) can be upgraded at an expense of cost (ital (v)). Such an upgrade reduces the cost of each edge incident on (ital v) by a fixed factor (rho), where 0 < (rho) < 1. For a given budget, (ital B), the goal is to find an improvement strategy such that the total cost of reduction is a most the given budget (ital B) and the cost of a subgraph (e.g. minimum spanning tree) under the modified edge lengths is the best over all possible strategies which obey the budget constraint. Define an ((alpha),(beta))-approximation algorithm as a polynomial-time algorithm that produces a solution within (alpha) times the optimal function value, violating the budget constraint by a factor of at most (Beta). The results obtained in this paper include the following 1. We show that in general the problem of computing optimal reduction strategy for modifying the network as above is (bold NP)-hard. 2. In the node based model, we show how to devise a near optimal strategy for improving the bottleneck spanning tree. The algorithms have a performance guarantee of (2 ln (ital n), 1). 3. for the edge based improvement problems we present improved (in terms of performance and time) approximation algorithms. 4. We also present pseudo-polynomial time algorithms (extendible to polynomial time approximation schemes) for a number of edge/node based improvement problems when restricted to the class of treewidth-bounded graphs.