论文部分内容阅读
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 between any two nodes of the network is below a pre-specific level. In the upgrading model, the improvement by upgrading one node is a continuous variable, and the cost incurred by such an upgrading is a linear function of the improvement. We show that achieving an approximation ratio βln(|V|) for the problem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. But if the underlying network is restricted as a tree, we show that it can be solved in a strongly polynomial time.
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 between any two nodes of the network is below a pre-specific level. improvement by upgrading one node is a continuous variable, and the cost incurred by such an upgrading is a linear function of the improvement. We show that achieving an approximation ratio βln (| V |) for the problem is NP-hard for some constant β > 0 even if the underlying network is a bipartite graph. But if the underlying network is restricted as a tree, we show that it can be solved in a great polynomial time.