AbstractThis paper introduces the power-p Steiner tree problem, which is to find a geometric Steiner tree that minimizes the sum of the edge lengths each raised to the p power. A number of results are presented on computing optimal and approximate power-p Steiner 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-p Steiner tree problem is not finitely solvable for p >= 5. Finally, bounds are given on the power-p Steiner ratio, which measures the quality of a minimum spanning tree as an approximation of an optimal power-p Steiner 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.