Broadcasting in heterogeneous networks

Samir Khuller*, Yoo Ah Kim

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1-21
Number of pages21
JournalAlgorithmica (New York)
Volume48
Issue number1
DOIs
StatePublished - Jun 1 2007

Keywords

  • Approximation algorithms
  • Broadcast
  • Multicast

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Broadcasting in heterogeneous networks'. Together they form a unique fingerprint.

Cite this