An Improved Approximation Ratio to the Partial-Terminal Steiner Tree Problem

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph${ G = (V,E)}$with a metric cost function${ c:E \rightarrow {\BBQ_ \geq }}$and two proper subsets$ R \subset V$and$ R^\prime \subseteq R$, a partial-terminal Steiner tree is a Steiner tree which contains all vertices in$\it R$such that all vertices in$R^\prime$must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in$G$. The previously best-known approximation ratio of the problem is$ 2\rho$, where$\bf \rho$is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from$ 2\rho$to$ 2\rho - {\rho \over {3\rho - 2}} - f$, where$f$is a non-negative function whose value is between 0 and$ \rho - {\rho \over {3\rho - 2}}$.