On the Partial-Terminal Steiner Tree Problem

Given a complete graph G = (V, E) with a length (or cost) function c : E rarr Qges and two proper subsets R subV and R¹subeR, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R´ must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum length in G. The previously best-known approximation ratio of the problem is 2rho, where p is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2rho to 2rho - (rho/(3rho-2))- epsi, where epsi is some non-negative number.