Node weighted network upgrade problems

Sven O. Krumke, Hartmut Noltemeier, Madha V. Marathe, S. S. RaviUniversity 1996

Abstract

Consider a network where nodes represent processors and edges represent bidirectional communication links. The processor at a node v can be upgraded at an expense of cost(v). Such an upgrade reduces the delay of each link emanating from v by a fixed factor x, where 0 < x < 1. The goal is to find a minimum cost set of nodes to be upgraded so that the resulting network has a spanning tree in which edge is of delay at most a given value {delta}. The authors provide both hardness and approximation results for the problem. They show that the problem is NP-hard and cannot be approximated within any factor {beta} < ln n, unless NP {improper_subset} DTIME(n{sup log log n}), where n is the number of nodes in the network. They then present the first polynomial time approximation algorithms for the problem. For the general case, the approximation algorithm comes within a factor of 2 ln n of the minimum upgrading cost. When the cost of upgrading each node is 1, they present an approximation algorithm with a performance guarantee of 4(2 + ln {Delta}), where {Delta} is the maximum node degree. Finally, they present a polynomial time algorithm for the class of treewidth-bounded graphs.
BibTeX
@inproceedings{krumke1996node,
  author = {Sven O. Krumke and Hartmut Noltemeier and Madha V. Marathe and S. S. Ravi},
  title = {{Node weighted network upgrade problems}},
  booktitle = {University},
  year = {1996},
}

Loading related content...

Figure