Approximation schemes for broadcasting in heterogeneous networks

Samir Khuller, Yoo-Ah Kim, Gerhard Woeginger

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

1 Citation (Scopus)

Abstract

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
Subtitle of host publication7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004. Proceedings
EditorsKlaus Jansen, Sanjeev Khanna, José D.P. Rolim, Dana Ron
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages163-170
Number of pages7
ISBN (Electronic)978-3-540-27821-4
ISBN (Print)978-3-540-22894-3
DOIs
Publication statusPublished - 2004
Event7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 - Cambridge, United States
Duration: 22 Aug 200424 Aug 2004
Conference number: 7

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3122
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004
Abbreviated titleAPPROX
CountryUnited States
CityCambridge
Period22/08/0424/08/04

    Fingerprint

Keywords

  • Completion time
  • Transmission time
  • Message pass interface
  • Multicast group
  • Polynomial time approximation scheme

Cite this

Khuller, S., Kim, Y-A., & Woeginger, G. (2004). Approximation schemes for broadcasting in heterogeneous networks. In K. Jansen, S. Khanna, J. D. P. Rolim, & D. Ron (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004. Proceedings (pp. 163-170). (Lecture Notes in Computer Science; Vol. 3122). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-540-27821-4_15