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 |