Microcanonical optimization algorithm for the Euclidean Steiner problem in Rn with application to phylogenetic...

The Euclidean Steiner tree problem in R(n) (ESTP) is that of finding the shortest interconnecting network spanning p given nodes in the Euclidean R(n), with the possible use of extra nodes. Combinatorial explosion precludes the use of exact methods for large high-dimensional ESTP instances, but very few heuristic approaches have so far been proposed for them. Here we introduce a microcanonical optimization algorithm that works over a topology-describing data structure associated to the ESTP solutions, and which is proven able to find close-to-minimum Steiner trees in reasonable computational time, even for configurations of up to p=50 points in n=50 dimensions. Moreover, its performance is shown to increase with n, which makes it especially suited for high-dimensional clustering problems such as those of phylogenetic inference, an instance of which is considered here.