Sublogarithmic approximation for telephone multicast

摘要

Consider a network of processors modeled by an n-vertex graph G = (V, E). Assume that the communication in the network is synchronous, i.e., occurs in discrete "rounds;" and in every round every processor is allowed to pick one of its neighbors, and to send it a message. The telephone k-multicast problem requires to compute a schedule with minimal number of rounds that delivers a message from a given single processor, that generates the message, to all the processors of a given set T subset of V, T = k, whereas the processors of V T may be left uninformed. The case T = V is called broadcast problem. Several approximation algorithms with a polylogarithmic ratio were suggested for these problems, and the upper bound on their approximation threshold stands currently on O (log k) and O (log n), respectively.