Premium
Experimental evaluation of a partitioning algorithm for the steiner tree problem in R 2 and R 3
Author(s) -
Ravada Sivakumar,
Sherman Alan T.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240802
Subject(s) - steiner tree problem , algorithm , mathematics , combinatorics , tree (set theory) , heuristic , approximation algorithm , euclidean geometry , norm (philosophy) , computer science , discrete mathematics , mathematical optimization , geometry , political science , law
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 the subproblems, and single‐and double‐edge reduction techniques to eliminate 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 partitioning algorithm is an effective practical heuristic, which in less time finds solutions roughly comparable with those computed by Smith's Algorithm. The partitioning algorithm depends on a parameter t through which 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 only other Steiner tree algorithm known for R 3 under the Euclidean norm. Using uniformly generated point sets in the d ‐cube [0, 100] d , we compare the running time and solution quality for the partitioning algorithm 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 points, 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 points, our distributed implementation with t = 10 typically found within 22 seconds a Steiner tree within 1% of the cost (1059) of that computed by Smith's Algorithm in 200 seconds. At t = 31 and using approximately 108 seconds, our distributed implementation usually found slightly better Steiner trees than did Smith's Algorithm. © 1994 by John Wiley & Sons, Inc.