Approximations for Steiner trees with minimum number of Steiner points (Q5927652)

Given a set \(X\) of \(n\) points -- terminals -- in the Euclidean plane and a positive constant \(R\), determine the minimal number of points other than those in \(X\) -- Steiner points -- and a tree \(T\) spanning the corresponding superset of \(X\) such that edge in the tree has an Euclidean length no greater than \(R\). This problem, which is NP-hard, has applications in VLSI design, wavelength -- division multiplexing optical network design and wireless communications. As the first result the authors present Theorem 1: The steinerized minimum spanning tree is a polynomial-time approximation with performance ratio exactly 4. When the minimum spanning tree of \(X\) is a feasible solution, then it also optimal with no Steiner points. Otherwise, we \(\text{add} \lceil|a,b\mid/ R\rceil\) Steiner points to break each edge ab into small pieces of lengths at most \(R\). As the second result the authors present a new approximation algorithm which yields performance no greater than ratio 3. This algorithm runs in \(O(n^4)\) time. In the last section a polynomial time approximation algorithm with performance ratio \(1+[16(4+3 \log k)c/k]\) is presented, where \(k\) denotes the size of used partitions and the length of the longest edge in the minimum spanning tree of \(X\) is at most \(c\) times of the length of the shortest one. Overall, this very interesting paper is clearly written despite some gaps in the text. For example, the proof of Theorem 1 does not contain the phrase ``polynomial-time'' at all. The authors present new valuable results so that anyone interested in the Steiner tree problem should find this paper worth reading.