Packing trees in communication networks

Given an undirected edge–capacitated graph and given (possibly) different subsets of vertices, we consider the problem of selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming (ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem with exponentially many variables and a block (sub–)problem that cannot be solved in polynomial time. To this end, we take an r–approximate block solver (a weak block solver) to develop a (1–e)/r–approximation algorithm for the LP relaxation.