Polynomial time approximation scheme for the rectilinear Steiner arborescence problem

Given a set N of n terminals in the first quadrant of the Euclidean plane E -2, find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called r ectilinear Steiner arborescence problem, which has been proved to be NP-com plete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial ti me approximation scheme for this problem.