EXPERIMENTAL EVALUATION OF A PARTITIONING ALGORITHM FOR THE STEINER TREE PROBLEM IN R(2) AND R(3)

We experimentally evaluate sequential and distributed implementations of an approximation partitioning algorithm by Kalpakis and Sherman for the Geometric Steiner Minimum Tree Problem (GSMT) in R(d) for d = 2, 3. Our implementations incorporate an improved method for combining th e subproblems, and single-and double-edge reduction techniques to elim inate unnecessary Steiner points created by the partitioning process. Results show that these refinements are crucial in practice to produce high-quality results. Moreover, with these refinements, the partition ing algorithm is an effective practical heuristic, which in less time finds solutions roughly comparable with those computed by Smith's Algo rithm. The partitioning algorithm depends on a parameter t through whi ch the user can trade off time for solution quality. To solve each of the subproblems of size at most t, we apply Smith's Algorithm, the onl y other Steiner tree algorithm known for R3 under the Euclidean norm. Using uniformly generated point sets in the d-cube [0, 100]d, we compa re the running time and solution quality for the partitioning algorith m for various values of t against that of Smith's Algorithm applied to the entire input. We also estimate the constant factor in the 1 + O(t -1/d(d-1) asymptotic performance bound proven by Kalpakis and Sherman and find that it is less than one. With d = 2 on input sets of 25 poin ts, our sequential implementation with t = 7 typically found within 6 seconds a Steiner tree within 1% of the cost (342) of that computed by Smith's Algorithm in 20 seconds. At t = 13 and using approximately 15 seconds, our sequential implementation typically found Steiner trees within 0.1% of this cost. Similarly, with d = 3 on input sets of 60 po ints, our distributed implementation with t = 10 typically found withi n 22 seconds a Steiner tree within 1% of the cost (1059) of that compu ted by Smith's Algorithm in 200 seconds. At t = 31 and using approxima tely 108 seconds, our distributed implementation usually found slightl y better Steiner trees than did Smith's Algorithm. (C) 1994 John Wiley & Sons, Inc.