AbstractThis paper introduces the power-

pSteiner tree problem, which is to find a geometric Steiner tree that minimizes the sum of the edge lengths each raised to theppower. A number of results are presented on computing optimal and approximate power-pSteiner trees. Specifically, a linear-time numerical algorithm is presented for computing optimal Euclidean power-2 Steiner trees with respect to a given topology, and the algorithm is proved to be numerically stable. It is conjectured, and strong evidence given, that the power-pSteiner tree problem is not finitely solvable forp>= 5. Finally, bounds are given on the power-pSteiner ratio, which measures the quality of a minimum spanning tree as an approximation of an optimal power-pSteiner tree.

Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.1 [Numerical Analysis]; G.2 [Discrete Mathematics]

Additional Key Words and Phrases: Steiner tree, geometric algorithms, approximation, facility location

Selected references

- David Lichtenstein. Planar formulae and their uses. SIAM Journal on Computing, 11(2):329-343, May 1982.

- Warren D. Smith. How to find Steiner minimal trees in Euclidean
d-space. Algorithmica, 7:137-177, 1992.