language: en

Approaching the 5/4-Approximation for Rectilinear Steiner Trees

Piotr Berman Ulrich Fomeier Marek Karpinski Michael Kaufmann Alexander Zelikovsky
September 29, 1995

Abstract The rectilinear Steiner tree problem requires a shortest tree spanning a given vertex subset in the plane with rectilinear distance. It was proved that the output length of Zelikovsky's [25] and Berman/Ramaiyer [3] heuristics is at most 1.375 and 97 72 1:347 of the optimal length, respectively. It was claimed that these bounds are not tight. Here we improve these bounds to 1.3125 and 61 48 1:271, respectively, and give efficient algorithms to find approximations of such quality. We also prove that for Zelikovsky's heuristic this bound cannot be less than 1.3.

Keywords: Algorithms, approximations, Steiner tree

1 Introduction