New approximation algorithms for routing with multiport terminals

Previous literature on very large scale integration routing and wiring esti mation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layo ut steps such as wiring estimation. In this paper, we address the general p roblem of minimum-cost routing tree construction in the presence of multipo rt terminals, which gives rise to the group Steiner minimal tree problem. O ur main result is the first known approximation algorithm for the group Ste iner problem with a sublinear performance bound. In particular, for a net w ith k multiport terminals, previous heuristics have a performance bound of (k - 1) . OPT, while our construction offers an improved performance bound of 2 . (2 + 1n(k/2)) . rootk . OPT. Our Java implementation is available on the Web.