3. A Graph Steiner Tree Heuristic

A number of heuristics were proposed over the years for the GSMT problem [9], two of which have performance bounds of a constant factor from optimal:

• KMB -- the heuristic of Kou, Markowsky and Berman [12] with a performance bound of 2 times optimal; and
• ZEL -- the more recent heuristic of Zelikovsky [20] with performance bound of 11/6 times optimal.

We propose a method of iterating heuristics for the GSMT problem. Recall that an instance of the GSMT problem is a weighted graph G=(V,E) and a net N subset of V, with the objective being finding a minimum-cost tree in G that spans N. For any existing graph Steiner tree heuristic H, let H(G,N) denote the solution that H produces, and let cost(H(G,N)) denote the cost of that solution. Our algorithm accepts as input an instance of the GSMT problem and any existing GSMT heuristic H. It then repeatedly finds Steiner node candidates that reduce the overall spanning cost with respect to H, and includes them into the growing set of Steiner nodes S.

Definition 3.1 Given a set of Steiner candidate nodes S subset of V - N, the cost savings of S with respect to H is: Delta H ( G, N, S ) = cost( H ( G, N )) - cost( H ( G, N U S )).

Starting with an initially empty set of Steiner nodes S = Ø, our heuristic finds a node t in V - N which maximizes Delta H( G, N, S U { t }) > 0 and repeats this procedure with S = S U { t }. The cost for H to span N U S will decrease with each added node t, and the construction terminates when there is no t in (V - N) - S such that Delta H( G, N, S U { t } ) > 0. The output solution is H( G, N U S ). This general template, which we call the Iterated Graph Steiner Minimal Tree (IGSMT) approach, is formally described in Figure 4.

Iterated Graph Steiner Minimal Tree Algorithm 

Input: A weighted graph G=(V,E), a net N subset of V
       and a GSMT heuristic H
Output: A low-cost tree T'=(V',E') spanning N, where
        N subset of V' subset of V and E' subset of E

S = Ø
Do Forever
    T = { t in V - N | Delta H( G, N, S U {t}) > 0 }
    If T = Ø Then Return H(G, N U S)
    Find t in T with maximum Delta H( G, N, S U {t})
    S = S U {t}

                 Figure 4: The IGSMT algorithm.

The performance bound of the IGSMT method is no worse than that of the heuristic H, since if no improving Steiner nodes can be found, the output of IGSMT will be identical to the output of H. For example, we may use the ZEL heuristic [20] as H inside the IGSMT template to yield the Iterated ZEL (IZEL) method, which inherits ZEL's performance bound of < 11/6 times optimal. Note that IGSMT generalizes the Iterated 1-Steiner heuristic of Kahng and Robins [10] (where H is an ordinary rectilinear minimum spanning tree construction), as well as the algorithms of [1,2] (where H is the KMB heuristic). Our experimental results indicate that iterating a heuristic H in this fashion yields significantly improved solutions as compared with the non-iterated version of H.

The time complexity of IGSMT depends on the particular heuristic H that is used. A naive implementation (which treats H as a "e;black box"e; subroutine) will have time complexity O(|N|*|V|* t(H) ), where t(H) is the time complexity of H. This time complexity may be substantially improved by (1) extracting out of H common computations (e.g., computing shortest-paths), to avoiding duplication of effort among multiple calls to H, and by (2) adding Steiner points in "e;batches"e; based on a non-interference criterion [8,10].