A NEW CLASS OF ITERATIVE STEINER TREE HEURISTICS WITH GOOD PERFORMANCE

The minimum rectilinear Steiner tree (MRST) problem is very important for such aspects of physical layout as global routing and wiring estimation. Virtually all previous heuristics for computing rectilinear Steiner trees begin with a minimum spanning tree (MST) topology and rearrange edges to induce Steiner points. This paper gives a more direct approach which makes a significant departure from such spanning tree-based strategies: we iteratively find optimal Steiner points to be added to the layout. Our method not only gives improved average-case performance, but also escapes the worst-case examples of existing approaches. We show that the performance ratio of our method can never be as bad as 3/2, and is in fact bounded by 4/3 on the entire class of instances where the c(MST)/c(MRST) cost ratio is exactly 3/2. Sophisticated computational geometry techniques allow efficient and practical implementation, and the method is naturally suited to technological regimes where, e.g., via costs can be high and the number of Steiner points should be limited. Extensive performance results show a 2% to 3% wire length reduction over the best previous heuristics. We describe a number of variants and extensions, and suggest directions for further research.