Approximation algorithm for multicast k-tree routing problem
In the Multicast k-Tree Routing Problem the input consists of the following parts: A simple, complete, undirected, weighted graph G with nodes set V, a source node s and a set of destination nodes D (that is a subset of V). The weight of an edge represents its length. Let k be a constant positive integer (and the value of k is a parameter of the problem). The goal is to find a partition of D into disjoint sets each of which of cardinality no more than k and for each subset in this partition to find a Steiner tree spanning the source node s and this subset of destination nodes (and perhaps additional nodes), so that the total length of these Steiner trees is minimized.
We use the randomized rounding technique to improve the known approximation ratios for this problem for all constant values of k.