ABSTRACT
The Steiner ratio in a metric space is the largest lower bound for the ratio of lengths between the Steiner minimum tree and the minimum spanning tree for the same set of points in the space. In the other words, it is the inverse of the performance ratio of the minimum spanning tree as an approximation of the Steiner minimum tree. A tree interconnecting a terminal set is called a Steiner tree if every leaf is a terminal. Starting from a minimum spanning tree, improve it by adding Steiner points. This is a natural idea to obtain an approximation solution for the Steiner minimum tree. A. Kahng and G. Robins proposed an approximation algorithm for the rectilinear Steiner tree by using the same idea as that of Chang. For rectilinear Steiner tree, crosspoints on a cut line can be moved to portals by increasing a small amount of the length.
