Improving minimum cost spanning trees by upgrading nodes

We study budget constrained network upgrading problems. We are given an und irected edge-weighted graph G = (V, E), where node upsilon E V can be upgra ded at a cost of c(upsilon). This upgrade reduces the weight of each edge i ncident on upsilon. The goal is to find a minimum cost set of nodes to be u pgraded 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 1. On the positive side, we provide a polynomial time approximation algorit hm 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 nod es in the graph. The solution produced by the algorithm satisfies the budge t constraint, and the cost of the upgrading set produced by the algorithm i s O(log n) times the minimum upgrading cost needed to obtain a spanning tre e of weight at most D. 2. In contrast, we show that, unless N-O subset of or equal to DTIME(n(O)(( log log n))), there can be no polynomial time approximation algorithm for t he problem that produces a solution with upgrading cost at most alpha < In 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(rt). This result continues to hold, with f(n) = n(k) being any polynomial, even when the di fference between the maximum and minimum edge weights is bounded by a polyn omial in n. 3. Finally, we show that using a sample binary search over the set of admis sible values, the dual problem can be solved with an appropriate performanc e guarantee, (C) 1999 Academic Press.