Optimum adaptation of a Steiner network
For researchers and practitioners using Steiner trees in dynamic environments, this provides a computationally efficient update method, though it is an incremental improvement over existing numerical optimization approaches.
The paper presents a first-order approximation method to efficiently update Steiner point positions in a Euclidean Steiner tree after terminal nodes are perturbed, with numerical examples showing effectiveness for both small and large perturbations.
The Euclidean Steiner tree problem, normally posed in two dimensions, seeks to connect a set of prescribed terminal nodes by placing additional nodes, known as Steiner points, with edges connecting such nodes either to another Steiner point or a terminal node, and with the placements minimising the sum of all the edge lengths of the associated tree. We consider a problem in which we start with a known solution to a Steiner tree problem, and the terminal positions are then perturbed. A first-order approximation theorem is established for efficiently updating the Steiner point positions to recover a Steiner tree solution after the perturbations to terminal nodes. Numerical examples illustrate the effectiveness of our approach (including a stepwise application for large perturbations) as well as its limitations.