Broadcasting in Heterogeneous Networks |
| |
Authors: | Samir Khuller Yoo-Ah Kim |
| |
Affiliation: | (1) Department of Computer Science, University of Maryland, College Park, MD 20742, USA;(2) Computer Science and Engineering Department, University of Connecticut, Storrs, CT 06269, USA |
| |
Abstract: | In this paper we study a well-known broadcasting heuristic for heterogeneous networks of workstations, called fastest node
first. We show that this heuristic produces an optimal solution for minimizing the sum of all completion times and, in addition,
produces a 1.5 approximation for the problem of minimizing the maximum completion time. We also develop a polynomial-time
approximation scheme for this problem. We extend these results to show that the same bounds can be obtained for the multicast
operation on such heterogeneous networks. In addition we show that the problem of minimizing the maximum completion time is
NP-hard, which settles the complexity of this open problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|