A new heuristic for rectilinear Steiner trees

The minimum rectilinear Steiner tree (RST) problem is one of the fundamenta l problems in the field of electronic design automation. The problem is NP- hard, and much work has been devoted to designing good heuristics and appro ximation algorithms; to date, the champion in solution quality among RST he uristics is the patched Iterated 1-Steiner (BI1S) heuristic of Kahng and Ro bins. In a recent development, exact RST algorithms have witnessed spectacu lar progress: The new release of the GeoSteiner code of Warme et al. has av erage running time comparable to that of the fastest available BI1S impleme ntation, 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 it s core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani 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 alg orithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation, Our heu ristic achieves a good running time by combining an efficient implementatio n of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real very large scale integrated i nstances show that the new RST heuristic runs significantly faster than Rob ins' implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than BI1S.