Faster approximation algorithms for the rectilinear Steiner tree problem

The classical Steiner tree problem requires a shortest tree spanning a given vertex subset within a graph G = (V, E). An important variant is the Steiner tree problem in rectilinear metric. Only recently two algorithms were found which achieve better approximations than the ‘traditional’ one with a factor of 3/2. These algorithms with an approximation ratio of 11/8 are quite slow and run in time O(n³) and O(n^5/2). A new simple implementation reduces the time to O(n^3/2). As our main result we present efficient parametrized algorithms which reach a performance ratio of 11/8+ϵ for any ϵ>0 in time O(n·log²m), and a ratio of 11/8 + log log n/log n in time O(n·log³n).