x, AND BARUCH

Abstract. In heterogeneous networks, sending messages may incur dierent delays on dierent links, and each node may have a dierent switching time between messages. The well studied Telephone model is obtained when all link delays and switching times are equal to one unit. We investigate the problem of nding the minimum time required to multicast a message from one source to a subset of the nodes of size k. The problem is NP-hard even in the basic Telephone model. We present a polynomial time algorithm that approximates the minimum multicast time within a factor of O(log k). Our algorithm improves on the best known approximation factor for the Telephone model by a factor of O log n log log k. No approximation algorithms were known for the general model considered in this paper