Approximation Schemes for Broadcasting in Heterogeneous Networks, Samir Khuller, Yoo-Ah

Abstract. We study the problem of minimizing the broadcast time for a set of processors in a cluster, where processor Ô � has transmission time Ø�, 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.