An adaptive algorithm for the Euclidean Steiner tree problem in d-space.
Aymeric Grodet, Takuya Tsuchiya · arXiv (Cornell University) · 2015
We describe a technique to improve Smith's branch-and-bound algorithm for the Euclidean Steiner tree problem in $\mathbb{R}^d$. The algorithm relies on the enumeration and optimization of full Steiner topologies for corresponding subsets of regular points. We handle the case of two Steiner points colliding during the optimization process - that is when they come to the same position - to dynamically change the exploration of the branch-and-bound tree. To do so, we present a way to reorganize a topology to another by exchanging neighbors of adjacent Steiner points. This enables reaching better minima faster, thus allowing the branch-and-bound to be further pruned. We also correct a mistake in Smith's program by computing a lower bound for a Steiner tree with a specified topology and using it as a pruning technique prior to optimization. Because Steiner points lie in the plane formed by their three neighbors, we can build planar equilateral points and use them to compute the lower bound, even in dimensions higher than two.