Improving Minimum Cost Spanning Trees by Upgrading Nodes

We study budget constrained network upgrading problems. We are given an undirected edge-weighted graph G = (V, E), where node v set membership, variant V can be upgraded at a cost of c(v). This upgrade reduces the weight of each edge incident on v. The goal is to find a minimum cost set of nodes to be upgraded so that the resulting network has a minimum spanning tree of weight no more than a given budget D. The results obtained in the paper include • On the positive side, we provide a polynomial time approximation algorithm for the above upgrading problem when the difference between the maximum and minimum edge weights is bounded by a polynomial in , the number of nodes in the graph. The solution produced by the algorithm satisfies the budget constraint, and the cost of the upgrading set produced by the algorithm is O (log ) times the minimum upgrading cost needed to obtain a spanning tree of weight at most . • In contrast, we show that, unless ⊆ (), there can be no polynomial time approximation algorithm for the problem that produces a solution with upgrading cost at most α < ln times the optimal upgrading cost even if the budget can be violated by a factor (), for any polynomial time computable function (). This result continues to hold, with () = being any polynomial, even when the difference between the maximum and minimum edge weights is bounded by a polynomial in . • Finally, we show that using a sample binary search over the set of admissible values, the dual problem can be solved with an appropriate performance guarantee.