A PTAS for the Grade of Service Steiner Minimum Tree Problem

Abstract

In this paper, we present the design of a PTAS(Polynomial Time Approximation Scheme) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. The previous research has focused on geometric analyses and different approximation algorithms were proposed. But having the PTAS, which provides a near-optimal solution, would be the conclusion for an optimization problem. This problem has some important applications. In the Network Design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions always provide paths with enough communication capacities between any two sites, with the least network construction costs. GOSST problem also has applications in transportation, for road constructions and some more potential uses in CAD in terms of interconnecting the elements on a plane such that to provide enough flux between any two elements.