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 l, t l ) }, 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.

Authors

• Peng Zhang
• Mingji Xia

Keywords

• k -Steiner Forest
• Greedy
• Set k -cover
• Approximation algorithm