Publication Details
Title: Approaching the 5/4-Approximation for Rectilinear Steiner Trees
Author: P. Berman, U. Fössmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky
Group: ICSI Technical Reports
Date: August 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-041.pdf
Overview:
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 Information:
ICSI Technical Report TR-94-041
Bibliographic Reference:
P. Berman, U. Fössmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky. Approaching the 5/4-Approximation for Rectilinear Steiner Trees. ICSI Technical Report TR-94-041, August 1994
Author: P. Berman, U. Fössmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky
Group: ICSI Technical Reports
Date: August 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-041.pdf
Overview:
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 Information:
ICSI Technical Report TR-94-041
Bibliographic Reference:
P. Berman, U. Fössmeier, M. Karpinski, M. Kaufmann, and A. Zelikovsky. Approaching the 5/4-Approximation for Rectilinear Steiner Trees. ICSI Technical Report TR-94-041, August 1994