Approximation Schemes for Broadcasting in Heterogenous Networks

Samir Khuller*, Yoo Ah Kim, Gerhard Woeginger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor pi has transmission time ti, which is the time taken to send a message to any other processor in the cluster. Previously, it was shown that the Fastest Node First method (FNF) gives a 1.5 approximate solution. In this paper we show that there is a polynomial time approximation scheme for the problems of broadcasting and multicasting in such a heterogenous cluster.

Original languageEnglish (US)
Pages (from-to)163-170
Number of pages8
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3122
StatePublished - Dec 1 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this