We address a practical problem which arises in several areas, including network design and VLSI circuit layout. Given an undirected weighted graph G = (V, E and a family N = [N1, …, Nk] of k disjoint groups of nodes Ni ⊆ V, the Group Steiner Problem asks for a minimum-cost tree which contains at least one node from each group Ni. In this paper, we give polynomial-time O(kϵ-approximation algorithms for any fixed ϵ > 0. This result improves the previously known O(k)-approximation. We also apply our approximation algorithms to the Steiner problem in directed graphs, while guaranteeing the same performance ratio. © 2001 John Wiley & Sons, Inc.

Previous literature on very large scale integration routing and wiring estimation 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 layout steps such as wiring estimation. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multiport terminals, which gives rise to the group Steiner minimal tree problem. Our main result is the first known approximation algorithm for the group Steiner problem with a sublinear performance bound. In particular, for a net with k multiport terminals, previous heuristics have a performance bound of (k-1)/spl middot/OPT, while our construction offers an improved performance bound of 2/spl middot/(2+1n(k/2))/spl middot//spl radic/k/spl middot/OPT. Our Java implementation is available on the Web.

Given a weighted graph and a family of k disjoint groups of nodes, the group Steiner problem asks for a minimum-cost routing tree that contains at least one node from each group. We give polynomial-time O(k/sup /spl epsiv//)-approximation algorithms for arbitrarily small values of /spl epsiv/>0, improving on the previously known O(k/sup 1/2 /)-approximation. Our techniques also solve the graph Steiner arborescence problem with an O(k/sup /spl epsiv//) approximation bound. These results are directly applicable to a practical problem in VLSI layout, namely the routing of nets with multi-port terminals. Our Java implementation is available on the Web.

Previous literature on VLSI routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however (say, in a gridded routing regime), each "terminal" consists of a large collection of electrically equivalent ports, a fact that is not accounted for in layout steps such as wiring estimation. The presence of multiple ports for a given terminal gives rise to the group Steiner minimal tree problem. In this paper, we address the general problem of minimum-cost routing tree construction in the presence of multi-port terminals. Our main result is the first known heuristic with a sub-linear performance bound. In particular, for a net with k multi-port terminals, previous heuristics have a performance bound of (k \\Gamma 1) \\Delta OPT , while our construction offers an improved performance bound of (1 + ln k 2 ) \\Delta p k \\Delta OPT . Our Java implementation is available on the World Wide Web.