In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pr...In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.展开更多
基金This research is supported by National Key Researchand Development Programof China(No.2002CB312004)and the National Outstanding Youth Fund.
文摘In this paper, we consider a network communication delay improvement problem,which is to upgrade nodes in a network with minimum cost such that the communication delay betweenany two nodes of the network is below a pre-specific level. In the upgrading model, the improvementby upgrading one node is a continuous variable, and the cost incurred by such an upgrading is alinear function of the improvement. We show that achieving an approximation ratio βln(|V|) for theproblem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. Butif the underlying network is restricted as a tree, we show that it can be solved in a stronglypolynomial time.
