An approximation algorithm to the k-Steiner Forest problem

Given a graph G, an integer k, and a demand set D = {(s(1), t(1)),..., (s(1), t(1))}, the k-Steiner Forest problem finds a forest in graph G to connect at least k demands in D such that the cost of the forest is minimized. This problem was proposed by Hajiaghayi and Jain in SODA'06. Thereafter, using a Lagrangian relaxation technique, Segev et al. gave the first approximation algorithm to this problem in ESA'06, with performance ratio O(n(2/3) log l). We give a simpler and faster approximation algorithm to this problem with performance ratio O(n(2/3) log k) via greedy approach, improving the previously best known ratio in the literature. (C) 2008 Elsevier B.V. All rights reserved.