Approximation schemes for broadcasting in heterogeneous networks

S. Khuller, Y.-A. Kim, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor p i has transmission time t i , 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
Title of host publicationApproximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004)
EditorsK. Jansen, xx et al.
Place of PublicationBerlin
ISBN (Print)978-3-540-22894-3
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Approximation schemes for broadcasting in heterogeneous networks'. Together they form a unique fingerprint.

Cite this