Approaching the 5/4-Approximation for Rectilinear Steiner Trees
Title | Approaching the 5/4-Approximation for Rectilinear Steiner Trees |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Berman, P., Fößmeier U., Karpinski M., Kaufmann M., & Zelikovsky A. |
Other Numbers | 911 |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-041.pdf |
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 |