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 language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
Subtitle of host publication | 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 |
Editors | Klaus Jansen, Sanjeev Khanna, José D.P. Rolim, Dana Ron |
Place of Publication | Berlin, Heidelberg |
Publisher | Springer |
Pages | 163-170 |
Number of pages | 7 |
ISBN (Electronic) | 978-3-540-27821-4 |
ISBN (Print) | 978-3-540-22894-3 |
DOIs | |
Publication status | Published - 2004 |
Event | 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 - Cambridge, United States Duration: 22 Aug 2004 → 24 Aug 2004 Conference number: 7 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 3122 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Workshop
Workshop | 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004 |
---|---|
Abbreviated title | APPROX |
Country/Territory | United States |
City | Cambridge |
Period | 22/08/04 → 24/08/04 |
Keywords
- Completion time
- Transmission time
- Message pass interface
- Multicast group
- Polynomial time approximation scheme