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 → BBQ ≥ and two proper subsets R ⊂ V and R´ ⊆ R, 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 cost in G. The previously best-known approximation ratio of the problem is 2ρ, where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2ρ to 2ρ- [(ρ)/(3ρ- 2)] - f, where f is a non-negative function whose value is between 0 and ρ- [(ρ)/(3ρ- 2)].