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^e)-approximation algorithms for arbitrarily small values of e>0, improving on the previously known O(k^0.5)-approximation. Our techniques also solve the graph Steiner arborescence problem with an O(k^e) 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.
Citation:
C. S. Helvig, Gabriel Robins, Alexander Zelikovsky, "Improved Approximation Bounds for the Group Steiner Problem," date, pp.406, Design Automation and Test in Europe (DATE '98), 1998