Improving minimum cost spanning trees by upgrading nodes

摘要

The authors study budget constrained network upgrading problems. The authors are given an undirected edge weighted graph (G = V, E) where node v (element-of) 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 the following: (1) on the positive side, they 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 n, the number of nodes in the graph, the solution produced by the algorithm satisfies the budget constrain, and the cost of the upgrading set produced by the algorithm is O (log n) times the minimum upgrading cost needed to obtain a spanning tree of weight at most D; (2) in contrast , they show that, unless NP (improper-subset) DTIME (n(sup O(log log n))), there can be no polynomial time approximation algorithm for the problem that produces a solution with upgrading cost at most (alpha) < ln n times the optimal upgrading cost even if the budget can be violated by a factor f(n), for any polynomial time computable function f(n), this result continues to hold, with f(n) = n(sup k) being any polynomial, even when the difference between the maximum and minimum edge weights is bounded by a polynomial in n; and (3) finally, they show that using a simple binary search over the set of admissible values, the dual problem can be solved with an appropriate performance guarantee.