Approximation ratio 2 for the Minimum number of Steiner Points

Abstract

This paper provides an approximation algorithm for STP-MSP(Steiner Tree Problem with Minimum number of Steiner Points). Because it seems to be impossible to have a PTAS(Polynomial Time Approximation Schemes), which gives the near optimal solutions, for the problem, the algorithm of this paper is an alternative that has the approximationratio 2 with a polynomial run time. The importance of this paper is the potential to solve other related unsolved problems. The idea of this paper is to distribute the error allowance over the problem instance so that we may reduce the run time to polynomial bound out of infintely many cases.