On Broadcasting in Heterogenous Networks

Samir Khuller*, Yoo Ah Kim

*Corresponding author for this work

Research output: Contribution to conferencePaper

26 Scopus citations

Abstract

In this paper we study a well known broadcasting heuristic for heterogenous 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 extend these results to show that the same bounds can be obtained for the multicast operation on such heterogenous 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.

Original languageEnglish (US)
Pages1004-1013
Number of pages10
StatePublished - Apr 15 2004
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On Broadcasting in Heterogenous Networks'. Together they form a unique fingerprint.

  • Cite this

    Khuller, S., & Kim, Y. A. (2004). On Broadcasting in Heterogenous Networks. 1004-1013. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.