An Improved Approximation Algorithm for Multicast <Emphasis Type="Italic">k</Emphasis>-Tree Routing

An improved approximation algorithm is presented in this paper for the multicast k-tree routing problem. The algorithm has a worst case performance ratio of (2.4 + ρ), where ρ is the best approximation ratio for the metric Steiner tree problem (and is about 1.55 so far). The previous best approximation algorithm for the multicast k-tree routing problem has a performance ratio of 4. Two techniques, weight averaging and tree partitioning, are developed to facilitate the algorithm design and analysis.Research supported by AICML, CFI, NSERC, PENCE, a Startup Grant from the University of Alberta, and NNSF Grant 60373012.