Approximating Steiner trees and forests with minimum number of Steiner points

Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies some connectivity properties. Let Delta be the maximum number of independent points in a unit ball. For the Steiner Tree with Minimum Number of Steiner Points problem we obtain approximation ratio 1 + In(Delta - 1) +epsilon, which in R-2 reduces to 1 + In 4 +epsilon < 2.3863 +epsilon; this improves the ratios [(Delta + 1)/2 ] + 1 +epsilon of [19] and 2.5 + epsilon of [7], respectively. For the Steiner Forest with Minimum Number of Steiner Points problem we give a simple Delta-approximation algorithm, improving the ratio 2(Delta - 1) of [21]. We also simplify the Delta-approximation of [4], when G[R boolean OR S] should be 2-connected. (C) 2018 Elsevier Inc. All rights reserved.