Approximation algorithm for directed telephone multicast problem Conference Paper uri icon

abstract

  • Consider a network of processors modeled by an n-vertex directed graph G=(V, E). Assume that the communication in the network is synchronous, ie, occurs in discrete “rounds”, and in every round every processor is allowed to pick one of its neighbors, and to send him 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 τ ⊆ V,\left| τ\right|= k. The processors of V $ τ maybeleftuninformed.Thetelephonemulticastisabasicprimitiveindi….Inthispaperwedeviseanalgorithmthatconstru… (maxlogk,logn/logk•br*+k1/2)roundsforthedirectedk-multicastproblem,wherebr* isthevalueoftheoptimumsolution.Thissignificantlyimprovesthepreviouslybest- knownapproximationratioofO(k1/3•logn•br*+k2/3)duetoEK03 …

publication date

  • June 30, 2003