New Approximation Algorithms for the Steiner Tree Problems

TitleNew Approximation Algorithms for the Steiner Tree Problems
Publication TypeTechnical Report
Year of Publication1995
AuthorsKarpinski, M., & Zelikovsky A.
Other Numbers976
KeywordsApproximation Algorithms, Approximation Ratio, Network Steiner Tree Problem, Rectilinear Steiner Tree Problem

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.

Bibliographic Notes

ICSI Technical Report TR-95-036

Abbreviated Authors

M. Karpinski and A. Zelikovsky

ICSI Publication Type

Technical Report