Improving Minimum Cost Spanning Trees by Upgrading Nodes

• Published in: Journal of algorithms 1999-10, Vol.33 (1), p.92-111
• Main Authors: Krumke, S.O, Marathe, M.V, Noltemeier, H, Ravi, R, Ravi, S.S, Sundaram, R, Wirth, H.-C
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; approximation algorithms; bicriteria problems; combinatorial algorithms; Computer science; control theory; systems; Exact sciences and technology; Information retrieval. Graph; network design; spanning trees; Theoretical computing
• ISSN: 0196-6774; 1090-2678
• DOI: 10.1006/jagm.1999.1021

We study budget constrained network upgrading problems. We are given an undirected edge-weighted graph G=(V,E), where node v∈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 α