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.
|Title of host publication||Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Proceedings APPROX 2004 and RANDOM 2004, Cambridge MA, USA, August 22-24, 2004)|
|Editors||K. Jansen, xx et al.|
|Place of Publication||Berlin|
|Publication status||Published - 2004|
|Name||Lecture Notes in Computer Science|