Packing element-disjoint steiner trees

Given an undirected graph G ( V , E ) with terminal set T ⊆ V , the problem of packing element-disjoint Steiner trees is to find the maximum number of Steiner trees that are disjoint on the nonterminal nodes and on the edges. The problem is known to be NP-hard to approximate within a factor of Ω(log n ), where n denotes | V |. We present a randomized O (log n )-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of O (log n ) on the integrality ratio of a natural linear programming relaxation.