A 3.4713-approximation algorithm for the capacitated multicast tree routing problem

Given an underlying communication network represented as an edge-weighted graph G = ( V, E ), a source node s ∈ V, a set of destination nodes D ⊆ V, and a capacity k which is a positive integer, the capacitated multicast tree routing problem asks for a minimum cost routing scheme for source s to send data to all destination nodes, under the constraint that in each routing tree at most k destination nodes are allowed to receive the data copies. The cost of the routing scheme is the sum of the costs of all individual routing trees therein. Improving on our previous approximation algorithm for the problem, we present a new algorithm which achieves a worst case performance ratio of 2089 + 77 80 + 5 4 ρ, where ρ denotes the best known approximation ratio for the Steiner minimum tree problem. Since ρ is about 1. 55 at the writing of the paper, the ratio achieved by our new algorithm is less than 3. 4713. In comparison, the previously best ratio was 8 5 + 5 4 ρ ≈ 3. 5375.

Authors

• Zhipeng Cai Intel Labs
• Zhi-Zhong Chen
• Guohui Lin

Keywords

• Capacitated multicast tree routing
• Approximation algorithm
• Steiner minimum tree
• Tree partitioning