A Near-Optimal Approximation Algorithm for Manhattan Steiner Tree
近乎最佳的Manhattan型Steiner树近似算法

The minimum rectilinear Steiner tree (MRST) problem is an NP-complete problem which arises in VLSI wiring,network routing and many combinatorial optimization problems.In this paper,an O(n2) time complexity approximation algorithm for MRST is proposed.The approximation ratio of the algorithm is strictly less than 3/2.The computer verification of the algorithm shows that the costs of the produced spanning trees are only 0.8% away from the optimal.In addition,this algorithm can be revised for multidimensional Manhattan space and implemented in parallel/distributed environments easily.