A new heuristic for rectilinear Steiner trees

The minimum rectilinear Steiner tree (RST) problem is one of the fundamental problems in the field of electronic design automation. The problem is NP-hard, and much work has been devoted to designing good heuristics and approximation algorithms; to date, the champion in solution quality among RST heuristics is the Batched Iterated 1-Steiner (BI1S) heuristic of Kahng and Robins (1992). In a recent development, exact RST algorithms have witnessed spectacular progress: the new release of the GeoSteiner code of Warme, Winter, and Zachariasen (1998) has average running time comparable to that of the fastest available Bl1S implementation, due to Robins. We are thus faced with the paradoxical situation that an exact algorithm for an NP-hard problem is competitive in speed with a state-of-the-art heuristic for the problem. The main contribution of this paper is a new RST heuristic, which has at its core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani (1999) for the metric Steiner tree problem on quasi-bipartite graphs-these are graphs that do not contain edges connecting pairs of Steiner vertices. The RV algorithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation. Our heuristic achieves a good running time by combining an efficient implementation of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real VLSI instances show that the new RST heuristic runs significantly faster than Robins´ implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than Bl1S.