A polynomial time approximation scheme for the grade of service steiner minimum tree problem

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

6 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)437-448
Journal / PublicationJournal of Global Optimization
Issue number4
Publication statusPublished - Dec 2002


In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+ . The GOSST problem has some important applications. In 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 should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements. © 2002 Kluwer Academic Publishers.

Research Area(s)

  • Approximation algorithms, Grade of service Steiner minimum tree, Network design, Rectangular partitions