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 language | English (US) |
---|---|
Pages (from-to) | 163-170 |
Number of pages | 8 |
Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
Volume | 3122 |
State | Published - Dec 1 2004 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)