Approaching the 5/4-Approximation for Rectilinear Steiner Trees

TitleApproaching the 5/4-Approximation for Rectilinear Steiner Trees
Publication TypeTechnical Report
Year of Publication1994
AuthorsBerman, P., Fößmeier U., Karpinski M., Kaufmann M., & Zelikovsky A.
Other Numbers911

The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of Zelikovsky's [17] heuristic is between 1.3 and 1.3125 (before it was only bounded from above by 1.375), while the performance ratio of the heuristic of Berman and Ramaiyer [1] is at most 1.271 (while the previous bound was 1.347). Moreover, we provide O(n*log2n)-time algorithms that satisfy these performance ratios.

Bibliographic Notes

ICSI Technical Report TR-94-041

Abbreviated Authors

P. Berman, U. Fössmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky

ICSI Publication Type

Technical Report