An improved approximation algorithm for the partial-terminal Steiner tree problem with edge cost 1 or 2

Given a complete graph G = (V, E) with a metric cost function C: E -> R+ and two vertex subsets R subset of V and R' subset of R, a partial-terminal Steiner tree is a Steiner tree which contains all the vertices in R such that all the vertices in R' are leaves. The partial-terminal Steiner tree problem (PTSTP) is to find a partial-terminal Steiner tree with the minimum cost. The problem has been shown to be NP-hard and MAX SNP-hard, even when the edge costs are restricted in {1, 2}, namely, the (1, 2)-partial-terminal Steiner tree problem (PTSTP(1, 2)). In this paper, we consider PTSTP(1, 2). The previous best-known approximation ratio of PTSTP(1, 2) was at most 25/14. In this paper, we propose a polynomial-time approximation algorithm that improves the approximation ratio from 25/14 to 5/3 (C) 2015 Elsevier B.V. All rights reserved.